[LeetCode] 用圖片來解釋怎麼解 #14 Longest Common Prefix
這題真的很直覺垂直掃描一次就是最直覺又最有效率的解法。
來看 GIF
如果 strs 有三個 strings，那我們就從左到右一排一排慢慢掃:
要掃到什麼時候? 我們想要讓大家前面都長得一樣，所以就掃到:
- 遇到不合群的字元的時候
- 或是某個字串太短，早就超過他的尾巴了
所以前面最長的 substring 就會是出現分歧的前一刻:
來寫 C++ Code
一開始我們就先這樣寫:
class Solution {
public:
std::string longestCommonPrefix(std::vector<std::string> &strs) {
const std::string &firstStr = strs.at(0);
for (size_t i = 0; i < firstStr.length(); i++) {
const char c = firstStr.at(i);
for (size_t otherIndex = 1; otherIndex < strs.size(); otherIndex++) {
const std::string &otherStr = strs.at(otherIndex);
if (i >= otherStr.size() || otherStr.at(i) != c) {
return firstStr.substr(0, i);
}
}
}
return firstStr;
}
};
別忘記如果 function 要 return 東西，如果掃到最後跑出 for loop 外就代表大家都長一樣，那就隨便抓一個 strs 裡面的 string 回傳。
讓程式快一點
我們觀察一下上面的 Code 發現每次 for loop 中都要做 i >= otherStr.size() 這會不會讓程式變慢呢?
再看一下上面的 gif 我們會發現其實只要跑到最短的字串就好了，其他人再長都沒有用。
那我們可以先偷算一下最短的字串是誰，那我們 index 最多就跑到最短字串的長度就好:
#include <algorithm>
class Solution {
public:
std::string longestCommonPrefix(std::vector<std::string> &strs) {
const std::string &firstStr = strs.front();
const size_t minLength = getMinLength(strs);
for (size_t i = 0; i < minLength; i++) {
const char c = firstStr.at(i);
for (size_t otherIndex = 1; otherIndex < strs.size(); otherIndex++) {
const std::string &otherStr = strs.at(otherIndex);
if (otherStr.at(i) != c) {
return firstStr.substr(0, i);
}
}
}
return firstStr.substr(0, minLength);
}
size_t getMinLength(const std::vector<std::string> &strs) {
size_t minLength = 200;
for (const auto &str : strs) {
minLength = std::min(str.length(), minLength);
}
return minLength;
}
};
不過可能這題的測資都太短，你看他的 constraints 部分 vector 和 string 的長度限制都只到 200，所以我丟上去是沒有發現什麼差異啦，兩個版本都大概 4ms 左右:
進階優化
記得以前上 parallel programming 之類的課都有說過，每次都跑去存取位置差很遠的記憶體位置時，電腦就無法好好利用 caching 的功能。
像上面這種 vertical scanning 其實每次都跑去不同的 string 去抓一個字元 cache 就沒什麼用，還是要跑去記憶體讀資料。
更好的做法當然是把 vertical scanning 的框框裡面的字元都擺在很鄰近的記憶體位置，但可能測資要非常大這樣做才會有用吧，別忘了我們還要先花力氣把資料轉個方式擺放。
結語
一開始我還以為要解 common substring 嚇死，想說 Easy 的題目怎麼突然就這麼進階了。
看到 LeetCode 提供的 solutions 裡面擺了那麼多解法更是嚇到，這到底是怎樣，為什麼要花這麼多力氣寫這麼多 overkill 的解法，你的測資又那麼小。
後面那個 trie 解法你就擺到真的是 repeated query 的題目去就好了，擺在這題是想要讓面試者有成就感，面試官又有時間可以多秀一些花樣嗎?
留言
發佈留言