問題連結: https://leetcode.com/problems/longest-absolute-file-path/
(CodeSignal — longestPath 也有同樣問題)
假設我們有一個檔案系統(file system)包含檔案們跟目錄如下
(用 ⟶ 代表tab字元, 有多少⟶代表他離根目錄(root directory)有多遠):
dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext如果我們用文字表示則會長這樣: "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
備註: '\n' 和'\t' 代表 換行 跟 tab 字元.
每個檔案和目錄在這個檔案系統中有一個唯一的絕對路徑, 這個絕對路徑代表著我們要到達某檔案或某資料夾前所需要按順序打開的資料夾們, 這些資料夾名稱會用/來做區隔開來
在上述例子中, file2.ext 的絕對路徑為"dir/subdir2/subsubdir2/file2.ext"各目錄名字包含字母, 數字, 或空格
各檔案名字皆會以name.extension的形式所示, name 和 extension 包含字母, 數字, 或空格
給予一個字串 input 代表檔案系統所包含的內容, 回傳這之中最長絕對路徑的檔案的路徑長度; 若檔案系統裡面沒有檔案, 則回傳0.
想法:
對我來說, 我覺得這題最難的部分是先讀懂很長的題目, 若這又是第一次遇到這題型, 很需要花耐心來把題目慢慢分解開來, 但如果你仔細看題目的範例, 其實我們可以總結成幾個小點來幫助我們解題:
- 題目給的input將會由資料夾名稱跟檔案名稱組成, 且他們各別都被換行字元'\n'來區隔
- 各名稱前tab('\t')的數目代表這個檔案或資料夾從根目錄往下數的階層, 舉例來說前面例子中, 我們看到在file1.ext前有兩個tab, 代表從根目錄往下我們需要進入(打開)兩個資料夾才能找到這個檔案
- 這題的目標就是找到檔案系統裡面有最長絕對路徑的檔案長度, 因此很重要的一點是 我們必須在找到任一檔案的時候, 知道它所屬的絕對路徑, 才能計算它的絕對路徑長度
因此我們第一個問題就是, 我們要如何得知我們現在所在檔案的絕對路徑?
根據我們發現的上述第一點, 我們可以用string.split()方法來去取得所有資料夾跟檔案名稱, 並把它們全放在一個字串陣列, 但下一步是我們要怎麼知道檔案跟其他哪些資料夾是有關連性的?
最理想的情況是我們在找到一個檔案名字的時候, 我們可以馬上知道哪些資料夾就是在這檔案之前, 因此我們就把這些資料夾名稱的長度加上檔案名字長度就可以得到現在檔案的絕對路徑長度, 或者更棒的是我們紀錄我們遇過的所有資料夾的絕對路徑長度, 在遇到這個檔案的時候, 我們就把遇到這檔案的前一個資料夾絕對路徑長度取出來, 加上我們檔案長度, 就會是這個檔案的絕對路徑長度了
下個問題就是, 那我們要用什麼資料結構來儲存這些資料夾的絕對路徑長度?
那我們先再次看我們的input 看可不可以發現什麼: "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
dir
⟶ subdir1
⟶ ⟶ file1.ext
⟶ ⟶ subsubdir1
⟶ subdir2
⟶ ⟶ subsubdir2
⟶ ⟶ ⟶ file2.ext若我們假設根目錄的level是0的話, 代表我們在這個例子中有兩個level 1的資料夾, 兩個level 2的資料夾, 一個level 2的檔案, 跟一個level 3的檔案
因此, 若我們想要知道level 2檔案的絕對路徑長度, 我們必須知道它的前一層level 1的資料夾絕對路徑長度, 若我們想要知道level 1的資料夾絕對路徑長度, 我們又必須要知道在這之前level 0的絕對路徑長度, 每個level的路徑長度其實都是由前面加總而來的
若我們隨時都加總好各自的絕對路徑, 代表當我們拿到level 1的長度時, 我們也不需回朔回去找level 0的長度, 而因為我們每次都只需要找最近期資料夾長度, stack堆疊所擁有的後進先出特性是個不錯的選擇
程式邏輯:
因此, 我們將用stack來記錄我們先前遇到的資料夾所在的絕對路徑長度, 而我們將會一直維持stack的大小等同於我們現在所在的階層, 會移除在stack中多餘的長度, 也就是說, stack中一個階層就會放一個資料夾的絕對路徑長度而已
舉例來說, 如果我們在level 2的資料夾時, 我們會依靠stack中最近期存放level 1的資料夾絕對路徑長度來判斷這個資料夾的絕對路徑長度, 但如果我們下一次又看到了另一個level 2的資料夾時, 我們將會把剛剛存放的level 2長度先拿掉, 再存放一次, 因為剛剛那個level 2的資料夾裡面也沒有檔案, 因此存它的長度已經沒有意義了, 因為若這個資料夾之後碰到的是一個檔案, 這個檔案會想知道的是它所在的資料夾長度, 不須知道同階層的其他資料夾路徑長
以下介紹幾個程式碼裡面會用的重要變數:
- splits: 一個字串陣列儲存所有的資料夾或檔案名稱
- stack: 一個堆疊儲存前面遇過的資料夾的絕對路徑長度
當我們儲存這些長度的時候, 我們都會假設資料夾後面有多一個/, 因此長度都會比他們實際絕對位置多1, 我們這樣的設計只是因為之後方便我們再往上在後面加檔案或資料夾的時候就可以直接把原本檔案或資料夾的名字長度往上加 - maxLen: 紀錄目前我們找到最長的絕對路徑檔案長度
- level: 現在這個資料夾或檔案所在的層級(根目錄為0, 層級就從根目錄要到現在位置多遠往上加), 我們會依照tab的數目來決定現在位置的層級
因為\t在Java中只佔了一個長度, 因此我們可以靠 找tab最後出現在這個名字的index+1來得知我們有幾個tab在名字之前 - curLen: 現在這個資料夾或檔案的名字長度(不包含其前面路徑), 且已把tab的長度們都已去除掉
- preLen: 在現在這個資料夾或檔案的上一層絕對路徑長度, 若我們現在正在根目錄, 則preLen為0
以下為3ms 程式碼, 贏過 23% —
public int lengthLongestPath(String input) {
int maxLen = 0;
String[] splits = input.split("\n");
Stack<Integer> stack = new Stack<>();
for(String cur: splits)
{
int level = cur.lastIndexOf("\t")+1;
int curLen = cur.length() - level;
while(stack.size() > level)
stack.pop();
int preLen = level==0? 0: stack.peek();
if(cur.contains("."))
maxLen = Math.max(maxLen, preLen+curLen);
else
stack.push(preLen+curLen+1);
}
return maxLen;
}我們也可以用一個陣列來代替使用Java的Stack來減少時間複雜度, 陣列中將儲存我們"最近期"某Level的絕對路徑長度, 因此我們不需要不斷的移除我們存的長度們, 在我們拿到level x的資料夾絕對路徑長度時, 我們會直接覆蓋我們之前存同level x的其他資料夾長度, 因為已經不需要用到了
因此我們可以得下面0ms的程式碼, 贏過 100% —
public int lengthLongestPath(String input) {
int maxLen = 0;
String[] splits = input.split("\n");
int[] stack = new int[splits.length+1];
for(String cur: splits)
{
int level = cur.lastIndexOf("\t")+1;
int curLen = cur.length() - level;
int preLen = level==0? 0: stack[level-1];
if(cur.contains("."))
maxLen = Math.max(preLen+curLen, maxLen);
else
stack[level] = preLen + curLen + 1;
}
return maxLen;
}
