主題
題目連結：
題目意譯：
給定一個目錄資訊之列表 paths，其包含目錄路徑以及包含所有目錄底下的所有檔案。根據檔案路徑，回傳檔案系統中所有重複的檔案。你可以按任意順序回傳答案。
一個重複檔案之群組由至少兩個檔案組成，其檔案內容相同。
一個輸入列表中目錄資訊字串有著以下格式：
"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) …… fn.txt(fn_content)"
其代表著目錄 "root/d1/d2/.../dm" 有著 n 的檔案（f1.txt 、 f2.txt …… fn.txt），而它們的內容為（f1_content 、 f2_content …… fn_content）。注意，n ≧ 1 且 m ≧ 0。如果 m = 0，則代表目錄為根目錄。
輸出為一個包含多個重複檔案之群組的列表。對於每個群組，其包含著所有內容相同的檔案之檔案路徑。一個檔案路徑有著以下格式：
"directory_path/file_name.txt"
（"目錄路徑/檔案名稱.txt"）
限制：
1 ≦ paths.length ≦ 2 × 10 ^ 4
1 ≦ paths[i].length ≦ 3000
1 ≦ sum(paths[i].length) ≦ 5 × 10 ^ 5
paths[i] 由英文字母、數字、'/' 、 '.' 、 '(' 、 ')' 和 ' ' 所組成。
你可以假設在同一個目錄底下沒有檔案或是目錄有著相同的名字。
你可以假設每個給定的目錄與其他目錄相異。目錄的路經和檔案資訊之間由一個空白字元隔開。
進階：
想像你被給定一個真實的檔案系統，你會怎麼搜尋檔案？ DFS 或 BFS？
如果檔案內容非常地大（GB 等級的），你會怎麼更動你的解法？
如果你每次只能讀取檔案中的 1kb ，你會怎麼更動你的解法？
你更動後的解法時間複雜度為何？其中最耗費時間以及最耗費記憶體的部分為何者？如何將其最佳化？
如何確保你找到的重複檔案不是偽陽性（False Positive）？
範例測資：
範例 1：
輸入： paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
輸出： [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]
範例 2：
輸入： paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"]
輸出： [["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]
解題思維：
對於 paths 中每個目錄資訊 paths[i]，按照空白將分開成多個子字串（如這題）。此時第一個字串是目錄的路徑，剩下的都是檔案名稱以及內容。
再將這些檔案的內容擷取出來，例如 "1.txt(abcd)" 、 "2.txt(efgh)" 的 "abcd" 和 "efgh" 。然後利用雜湊表（Hash Table）將 "abcd" 、 "efgh" 等內容對應到一個可變長度陣列（例如 C++ 中的 vector），而該陣列儲存的是內容為鍵值（內容）的檔案之路徑（目錄路徑 + 檔案名稱）。
最後對於每一種內容，根據雜湊表判斷該內容是否有多個檔案對應。如果是就將這些檔案名稱存進一個列表中。最後的所求就是這些列表再包進另一個列表裡。
進階：
一：根據現代人的使用習慣還有系統習慣的檔案建立方式，利用 DFS 會比 BFS 好。因為 BFS 需要佇列輔助，一旦同一層的目錄有著太多其他的目錄（例如系統檔案）會使佇列的大小不小；而 DFS 只需堆疊，堆疊的大小（高度）取決於最深的目錄的深度，而深度基本上都不會太深（通常不會到達三位數，但是同一層可能會有三位數的目錄）。
二：因為檔案很大，所以直接讀取整個檔案內容不實際。因此我們可以採用檔案的詮釋資料（Metadata，例如檔案大小、檔案路徑、修改以及建立時間等等）來當作雜湊的鍵值。不過如果雜湊表是自己寫的話，就需要自行處理碰撞（Collision）也就是多筆資料有著同一個鍵值的問題（內建的函式庫基本上都已經幫我們處理好這類問題了）。
三：如二的作法，讀取詮釋資料比較好。
四：時間複雜度取決於檔案數以及資料的大小（改用詮釋資料就會變得比較小了）。而整個過程最費時的就是雜湊的部分。
五：偽陽性的問題即代表著雜湊裡的「碰撞」，可以參見網路上處理碰撞的方式和演算法。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
