#40931: C++詳解-DFS+Map


toseanlin@gmail.com (Dr. SeanXD)

學校 : 康橋雙語學校
編號 : 158065
來源 : [24.147.249.5]
最後登入時間 :
2024-09-23 11:05:53
o078. 3. 缺字問題 -- 2024年6月APCS | From: [220.136.87.155] | 發表日期 : 2024-06-19 12:24

使用 DFS 去將所有組合計算出來,因為可以有重複的字元,所以 DFS 的參數只需要目前相加的字串。宣告一個 Map 來紀錄有哪些組合,這邊取名叫做 MAP,當 DFS 中的字串長度 == L 時,將 MAP[字串]++ 並且 return。

跑一個 For迴圈 從 0 到 S.length()-L,並且宣告另外一個 Map 來紀錄 S 中長度為 L 的子字串有哪些,這邊取名叫 appear。在裡面再跑一個 For迴圈 從目前的 i 到 i+L,要從目前的位置加字串加到 L 的長度。加完之後將 appear[剛剛加完的字串]++。

之後跑一個 for (auto it:MAP),要將剛剛 K 中的所有組合做判斷,如果 appear[it.first] == 0,代表 S 中沒有這個子字串,但是剛剛的 DFS 有計算出這個 it.first,這個就是答案,輸出 it.first 之後將迴圈 break。跑 for (auto it:MAP) 的時候會依照字串的順序跑,所以先跑到的就會是較小的字典序字串。

 

範例程式碼

 
ZeroJudge Forum