主題
題目連結：
題目意譯：
由於一個 bug，檔案系統中有多個重複的資料夾。你被給定一個二維陣列 paths，其中 paths[i] 為一陣列代表著一個第 i 個資料夾於檔案系統中的絕對路徑。
例如，["one", "two", "three"] 代表路徑 "/one/two/three"。
兩個資料夾（不一定於同一層中）為一致的（Identical）如果它們包含相同的「非空的相同子資料夾之集合」以及「隱含的子資料夾結構」。資料夾不一定要位在根目錄才能一致。如果兩個或多個資料夾是一致的，則將這些資料夾以及它們的子資料夾全數標記下來。
例如，資料夾 "/a" 和 "/b" 於以下的檔案結構中是一致的。它們（以及它們的子資料夾）應被標記：
/a
/a/x
/a/x/y
/a/z
/b
/b/x
/b/x/y
/b/z
不過，如果上列檔案結構多包含了 "/b/w" 這個路徑的話，則資料夾 "/a" 和 "/b" 便不再一致了。注意即使有了新加入的資料夾之後，"/a/x" 和 "/b/x" 仍會被視為是一致的。
一旦所有一致的資料夾以及它們的子資料夾都被標記後，檔案系統將會把它們全數刪除。該檔案系統只會執行一次的刪除，因此刪除後如有任何資料夾變為一致則不會被刪掉。
回傳一個二維陣列 ans 其包含著刪除所有標記的資料夾後剩餘的資料夾之路徑。路徑們彼此可以按任意順序排列。
限制：
1 ≦ paths.length ≦ 2 × 10 ^ 4
1 ≦ paths[i].length ≦ 500
1 ≦ paths[i][j].length ≦ 10
1 ≦ sum(paths[i][j].length) ≦ 2 × 10 ^ 5
path[i][j] 由小寫英文字母組成。
沒有兩個路徑導向到同一個資料夾。
對於任意一個不在根目錄的資料夾，其父母資料夾也將會出現在輸入中。
範例測資：
範例 1：
輸入： paths = [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]
輸出： [["d"],["d","a"]]
解釋： 檔案結構如圖所示。
資料夾 "/a" 和 "/c"（以及它們的子資料夾）被標記而後刪除因為它們兩者都包含著一個空資料夾名為 "b"。
範例 2：
輸入： paths = [["a"],["c"],["a","b"],["c","b"],["a","b","x"],["a","b","x","y"],["w"],["w","y"]]
輸出： [["c"],["c","b"],["a"],["a","b"]]
解釋： 檔案結構如圖所示。
資料夾 "/a/b/x" 和 "/w"（以及它們的子資料夾）被標記而後刪除因為它們兩者都包含著一個空資料夾名為 "y"。
注意到資料夾 "/a" 和 "/c" 在刪除後變為一致，但它們不會被刪除因為它們在先前並沒有被標記。
範例 3：
輸入： paths = [["a","b"],["c","d"],["c"],["a"]]
輸出： [["c"],["c","d"],["a"],["a","b"]]
解釋： 檔案系統中的所有資料夾皆是獨一無二的。
注意到回傳的陣列中的順序可與原先的不同，因為順序在此並不重要。
範例 4：
輸入： paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"]]
輸出： []
解釋： 檔案結構如圖所示。
資料夾 "/a/x" 和 "/b/x"（以及它們的子資料夾）被標記而後刪除因為它們兩者都包含著一個空資料夾名為 "y"。
資料夾 "/a" 和 "/b"（以及它們的子資料夾）被標記而後刪除因為它們兩者都包含著一個空資料夾名為 "z" 以及資料夾 "x"。
範例 5：
輸入： paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"],["b","w"]]
輸出： [["b"],["b","w"],["b","z"],["a"],["a","z"]]
解釋： 此與前一個例子有著相同的結構，除了新增的 "/b/w"。
資料夾 "/a/x" 和 "/b/x" 依舊會被標記，但是 "/a" 和 "/b" 不再會被標記因為 "/b" 有著一個空資料夾名為 "w" 而 "/a" 則無。
注意到 "/a/z" 和 "/b/z" 將不會被標記因為一致子資料夾之集合需為非空，但這些資料夾是空的。
解題思維：
先建立像是範例圖例中的樹狀檔案結構。接著從根節點（即根目錄「/」）開始按照深度優先搜尋（Depth First Search，DFS）的順序為每個節點利用雜湊（Hash）作為其簽章（Signature）之值，作法如下：
對於當前的節點，先遞迴求出其每個子資料夾各自的簽章。接著連同這些子資料夾的名稱以及簽章全數丟進雜湊便可以得到當前節點的簽章值。可以看到只要雜湊函數不要寫得太爛，簽章值一般會相異，只有輸入相同時會有相同的雜湊值。因此當有兩個資料夾雜湊值（簽章）相同時，我們可以認為兩個資料夾的內容物相同，即本題「一致」。
而我們再額外利用一個雜湊表用來儲存每種簽章各自有出現多少次，不過我們只需記錄那些有子資料夾的簽章，因為這些才是可能需要標記的資料夾（需為非空）。
最後我們再另外進行一次深度優先搜尋（Depth First Search，DFS），這次在遞迴的時候順便記錄目前從根目錄到此資料夾的路徑。
當我們每到一個節點時，我們先看此節點（資料夾）的簽章之值是否有在整個系統中出現超過一次以上（利用上面記錄簽章用的雜湊表）。如果有則代表此資料夾與其子資料夾們應被標記，所以不需再繼續遞迴，直接回上一層即可。
如果此資料夾的簽章只出現過一次，則我們便可以將到這個資料夾的「路徑」放到答案陣列之中，因為此資料夾將不會被標記，也就不會被刪除。接著就繼續遞迴探訪當前資料夾的每個子資料夾。
最後的答案陣列之內容物即為所有不會被刪除的資料夾，即所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
