[LeetCode] 偷懶直接寫 4 個 for loop 的解法 #17 Letter Combinations of a Phone Number
既然題目說最多只有 4 個 digit，我能不能用 4 個 for loop 直接解掉? 讓我們來看看。
懶人解法
如果 digits 是 "69"，那我先把要拿來組合的字串抽出來:
然後直接寫 4 個 for loop! 可是上面只有 2 個 string 怎麼辦? 我就多塞 2 個只有空白的 string 進去:
最後再移除空格就好。
C++ 程式碼就會長這樣:
class Solution {
public:
std::vector<std::string> letterCombinations(std::string digits) {
std::vector<std::string> words;
for (const char digit : digits)
words.push_back(m_wordList.at(digit - '2'));
while (words.size() < 4) words.push_back(" ");
std::vector<std::string> output;
for (size_t i1 = 0; i1 < words[0].length(); i1++) {
for (size_t i2 = 0; i2 < words[1].length(); i2++) {
for (size_t i3 = 0; i3 < words[2].length(); i3++) {
for (size_t i4 = 0; i4 < words[3].length(); i4++) {
std::string s = words[0].substr(i1, 1) + words[1].substr(i2, 1) +
words[2].substr(i3, 1) + words[3].substr(i4, 1);
s.erase(std::remove(s.begin(), s.end(), ' '), s.end());
if (s != "") output.push_back(s);
}
}
}
}
return output;
}
const std::vector<std::string> m_wordList = {
"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz",
};
};
沒有複雜的 DFS function 也沒有複雜的 BFS。
其實 for loop 還算是 DFS 的一種，但這樣是不是更好理解?
No! 一堆人會說這樣不 general! 萬一不只 4 個 digits 怎麼辦? 那就不要這樣寫。
我只有少數的情況真的會這樣寫:
- 對某個程式語言不熟的時候，像是 AutoHotKey 腳本語言我真的每次要用都忘記 syntax
- 程式碼用在不是很重要的地方的時候，像是寫 AutoHotKey 我只是懶，想寫個自動點東西的 script 有必要用 DFS/BFS?
- 想快速測試某個功能的時候，像是從來沒用過的 library，我想要快速驗證一些想法
所以真的完全不能這樣寫嗎? 我倒覺得未必。
DFS 解法
萬一教壞新手就不好了，所以我們還是來用圖像理解一下 DFS 解法。
簡單來說當你把要走的路在腦海中想像會變成 tree 的時候就可以用 DFS/BFS 了:
至於該用 DFS 還是 BFS 就看狀況了，這題這麼單純我會建議直接用 DFS 就好，用 BFS 太複雜了。
什麼時候要把 string 加到最後的結果? 就是當我們走到最底無法再走的時候，而上面的 function call 就慢慢把字元加在一起。
貼個網路上幾乎都找的到類似的解法:
class Solution {
public:
std::vector<std::string> letterCombinations(std::string digits) {
std::vector<std::string> output;
appendLetter(digits, 0, "", output /*will change*/);
return output;
}
void appendLetter(const std::string &digits, const int digitIndex,
const std::string &s, std::vector<std::string> &output) {
if (digitIndex >= digits.length()) {
if (s != "") output.push_back(s);
return;
}
const int wordIndex = digits.at(digitIndex) - '2';
const std::string &word = m_wordList.at(wordIndex);
for (const char c : word) {
const std::string newS = s + c;
appendLetter(digits, digitIndex + 1, newS, output /*will change*/);
}
}
const std::vector<std::string> m_wordList = {
"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz",
};
};
命名的話我看到很多人只有寫 dfs() 當作 function 名稱，是什麼東西的 DFS? 至少寫個 appendDfs 之類的會好一點。我這邊就乾脆不寫，直接寫我要 append 東西，DFS 什麼的只是一種方法而已。
結果
這題應該不管怎麼寫都會超快，就是一個給你練習 DFS/BFS 的基本題，面試也很好問
留言
發佈留言