---
tags: leetcode
---

# [71. Simplify Path](https://leetcode.com/problems/simplify-path/)
---
# My Solution
## The Key Idea for Solving This Coding Question
* [C++ Code 1](https://hackmd.io/steb3uL1QS6rmlvYgRahfw?view#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
<!--
# Test Cases

"/home/"

"/../"

"/home//foo/"

"/a/./b/../../c/"

"/hello../world"

"/..hidden"

"/."

"/..."

"/a//b////c/d//././/.."

"/../../.."

"/../.name/..../"

"/_123/.456/../"

"//////_123/////.456////////../////////"

"/a/b/c/d/e"

"/.."

-->