leetcode Simplify Path

leetcode Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c"

Corner Cases:

• Did you consider the case where path = "/../"? In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/". In this case, you should ignore redundant slashes and return "/home/foo".

题目地址：leetcode Simplify Path

题意：给定unix路径，要求进行简化。

思路：unix路径主要是用'/'进行区分 一个点表示当前目录，两个点表示上级目录。

可以按照 '/'进行划分，如果遇到'..'就数组中移出最后一个（就是个栈嘛），遇到‘.'就无视吧~

C++没有split函数，于是就来硬的。。(也可以用getline(ss, cur, '/')) 来划分

和Python相比。。py好简洁。

C++ getline version

class Solution {
public:
	string simplifyPath(string path) {
		stringstream ss(path);
		vector<string> q;
		string cur;
		while (getline(ss, cur, '/')) {
			if (cur == "") continue;
			if (cur == "..") { 
				if (!q.empty()) q.pop_back();
			}
			else if (cur != ".") q.push_back(cur);
		}
		string ans = "";
		for (string s : q) 	ans += "/" + s;
		return ans != "" ? ans : "/";
	}
};

 

C++

class Solution {
public:
	string simplifyPath(string path) {
		int n = path.length();
		stack<string> q;

		for (int i = 1; i < n; ){
			if (path[i] == '.'){				
				if (i + 1 < n && path[i + 1] == '.' && (i+2>=n ||i+2<n&& path[i+2]=='/')){
					if (!q.empty())
						q.pop();
					i += 3;
					continue;
				}
				else if (i + 1 < n && path[i + 1] == '/'){
					i += 2;
					continue;
				}				
			}
			int cur = path.find_first_of('/', i);
			if (cur == -1){
					string temp = path.substr(i, n - i);
					if (temp != " " && temp != "." && temp != "..")
						q.push(temp);
					break;
				}
			if (cur!=i)
				q.push(path.substr(i, cur - i));
			while (cur + 1 < n && path[cur + 1] == '/') cur++;
			i = cur + 1;
		}
		stack<string> q2;
		while (!q.empty()){
			q2.push(q.top());
			q.pop();
		}
		string ans="/";
		while (!q2.empty()){
			ans = ans + q2.top();
			q2.pop();
			if (!q2.empty())
				ans = ans + '/';
		}
		return ans;
	}
};

 

Python

class Solution:
    # @param path, a string
    # @return a string
    def simplifyPath(self, path):
        q=path.split('/')
        ans=[]
        for s in q:
            if s:
                if s=='..':
                    if len(ans) > 0:
                        ans.pop()
                elif s!='.':
                    ans.append(s)
        return '/'+'/'.join(ans)