71. Simplify Path

发表于 | 分类于 | 浏览 次

题目描述

Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.

In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix

Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.

Example 1:

1
2
3
Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

1
2
3
Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

1
2
3
Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Example 4:

1
2
Input: "/a/./b/../../c/"
Output: "/c"

Example 5:

1
2
Input: "/a/../../b/../c//.//"
Output: "/c"

Example 6:

1
2
Input: "/a//b////c/d//././/.."
Output: "/a/b/c"

#　解法1

思路：一次取出path中不等于//的部分（表示的是目录），若该部分是..，表示返回上级目录，若此时不在根目录下则有上级目录可以返回，则返回上级目录，即删除当前的目录。若该部分是.，表示当前目录，则什么也不做。否则，将新的目录加入到当前路径中（这里用vector来存储当前路径中的所有目录名）。最后将整个目录用/连接起来。另外，这里的根目录是隐含的，没有在初始化路径时加入到vector中，这是因为我们知道当前路径中的第一个目录一定是根目录。

注意：vector等的size()都是无符号数，无符号数都大于等于0，无符号数与有符号数做减法时不会产生负数，而是会变成一个很大的整数。参见：c++数据类型基础知识

AC代码：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    string simplifyPath(string path) {
        if(path.empty() || path[0]!='/'){
            return "";
        }
        vector<string> vec;
        int i=1;
        while(i < path.size()){
            int j=i;
            while(j < path.size() && path[j]=='/'){
                ++j;
            }
            i = j;
            while(j < path.size() && path[j]!='/'){
                ++j;
            }
            if(i < j){
                string tmp = path.substr(i, j-i);
                if(tmp == ".."){
                    if(!vec.empty()){
                        vec.pop_back();                        
                    }
                }else if(tmp !="."){
                    vec.push_back(tmp);
                }
            }
            i = j;
        }
        string res = "/";
        i = 0;
        while(vec.size() > 1 && i < vec.size()-1){
            res += vec[i];
            res += "/";
            ++i;
        }
        if(!vec.empty()){
            res += vec[vec.size()-1];
        }
        return res;
    }
};

复杂度分析

时间复杂度为为O(n)，只从左到右扫描了整个路径字符串一遍。
空间复杂度为O(n)，使用了一个vector来存储路径。