博文中会简要介绍Leetcode P0071题目分析及解题思路。

“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.

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:

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

Example 2:

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:

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

Example 4:

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

具体思路在这里就不再赘述，代码可读性比较强，大部分思路其实在代码中就已经体现了。

以下是Java的题解代码实现。

class Solution {
    public String simplifyPath(String path) {
        if (path == null || path.length() == 0)
            return path;
        
        Deque<String> paths = new LinkedList<>();
        for (String dir: path.split("/")) {
            if (dir.length() == 0 || ".".equals(dir))
                continue;
            
            if ("..".equals(dir)) {
                paths.pollLast();
            }
            else {
                paths.offerLast(dir);
            }
        }
        
        StringBuilder canonicalPath = new StringBuilder("/");
        for (String dir: paths) {
            canonicalPath.append(dir);
            canonicalPath.append("/");
        }
        
        // 如果不是根目录的路径
        if (canonicalPath.length() > 1)
            canonicalPath.deleteCharAt(canonicalPath.length()-1);
        
        return canonicalPath.toString();
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    string simplifyPath(string path) {
        if (path.length() == 0)
            return path;
        
        vector<string> dirs;
        stringstream ss(path);
        string dir;
        while (getline(ss, dir, '/')) {
            if (dir.length() == 0 || dir == ".")
                continue;
            
            if (dir == "..") {
                if (dirs.size() > 0)
                    dirs.pop_back();
            }
            else 
                dirs.push_back(dir);
        }
        
        string canonical_path = "/";
        for (int idx=0; idx<dirs.size(); ++idx) {
            canonical_path += dirs[idx];
            canonical_path += "/";
        }
          
        if (canonical_path.length() == 1)
            return canonical_path;
        
        return canonical_path.substr(0, canonical_path.length()-1);
    }
};