leetcode解题: Simplify Path (71)

发表于 | 分类于

Total Accepted: 74685
Total Submissions: 309287
Difficulty: Medium
Contributors: Admin
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".

解法1： Stack

比较清楚的思路是, 用一个stack来存储每一级的path, 如果遇到”.”则跳过,如果遇到”..”表明要前进一级, 那就把当前的栈顶的path弹出
最后栈就是存放的reverse过的path,一个个把他们串起来就可以了.
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
	string simplifyPath(string path) {
		stack<string> items;
		string item = "";
		stringstream ss(path);
		while(getline(ss, item, '/')) {
			if (item.size() == 0 || item == ".") {
				continue;
			} else if (item == "..") {
				if (!items.empty()) {
					items.pop();
				}
			} else {
				items.push(item);
			}
		}
		string res = "";
		while (!items.empty()) {
			res += "/" + items.top() + res;
		}
		return res.empty() ? "/" : res;
	}
};

也可以用一个deque来解决，这样在结束了之后不需要reverse stack里的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public String simplifyPath(String path) {
        Deque<String> deque = new LinkedList<String>();
        String[] comps = path.split("/");
        for (String comp : comps) {
            if (comp.equals("..")) {
                deque.pollLast();
            } else if (comp.equals(".") || comp.equals("")) {
                continue;
            } else {
                deque.offerLast(comp);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!deque.isEmpty()) {
            sb.append("/" + deque.pollFirst());
        }
        return sb.length() == 0 ? "/" : sb.toString();
    }
}