changed 3 years ago  
Published Linked with GitHub

71. Simplify Path

My Solution

The Key Idea for Solving This Coding Question

  • C++ Code 1
    要注意 path 的最後一個字元為 '\' 的這個特殊狀況。
    當 path 的最後一個字元為 '\' 時，第 17 行的 while 迴圈條件不成立，而停止對 name 的操作。在執行完第 22 ~ 33 行的程式後，第 7 行的最外層 while 迴圈的條件仍然成立 (因為此時 i 的值為path.size() - 1 )。所以仍會進入第 8 ~ 10 行的 while 迴圈，使得 i 的值更新為 path.size() 。那麼緊接著第 8 行的 while 迴圈條件失敗後，第 11 行的 if 條件成立，並執行第 13 行的 break ，然後離開第 7 ~ 34 行的整個 while 迴圈。
    這樣的設計是可以處理這個特殊狀況的一個辦法。

C++ Code 1
















































class Solution {
public:
    string simplifyPath(string path) {
        int i = 0;
        stack<string> st;

        while (i < path.size()) {
            while (i < path.size() && path[i] == '/') {
                ++i;
            }
            if (i >= path.size()) {
                // We have can the whole path.
                break;
            }

            string name;
            while (i < path.size() && path[i] != '/') {
                name.push_back(path[i]);
                ++i;
            }

            if (name == ".") {
                continue;
            }

            if (name == "..") {
                if (!st.empty()) {
                    st.pop();
                }
                continue;
            }

            st.push(name);
        }

        if (st.empty()) {
            return "/";
        }

        string answer;
        while (!st.empty()) {
            answer = "/" + st.top() + answer;
            st.pop();
        }
        return answer;
    }
};

C++ Code 2










































class Solution {
public:
    string simplifyPath(string path) {
        stack<string> st;
        
        for (int i = 1; i < path.size(); ++i) {
            string file;
            while (path[i] != '/' && i < path.size()) {
                file += path[i];
                ++i;
            }
            
            processStack(file, st);
        } // end of for-loop
        
        string answer;
        while (!st.empty()) {
            answer = st.top() + answer;
            st.pop();
        }
        if (answer.size() == 0) {
            answer = "/";
        }
        
        return answer;
    }
    
    void processStack(string& file, stack<string>& st) {
        if (file.size() == 0 || file == ".") {
            return;
        }
        if (file == "..") {
            if (!st.empty()) {
                st.pop();
            }
            return;
        }
        
        st.push("/" + file);
    }
};

Time Complexity

\(O(n)\)
\(n\) is the length of path.

Space Complexity

\(O(H + n)\)
\(n\) is the length of path.
\(H\) is the depth of the filesystem.

Miscellaneous

Select a repo