Leetcode No.3( Longest Common Prefix) 心得
題目:
Write a function to find the longest common prefix string amongst an array of strings.
翻譯:
找到一個字串陣列最長的共通前墜字串。
ex: {abcdef, abcabc, ab123} -> ab
想法:
這個題目沒有什麼特別之處,就是很簡單的先找一個字串,然後和另一個比對找出相同的前墜字串,然後依序找完整個陣列。
這題我花時間比較多在查詢vector和string有什麼library可以套用。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string prefix;
if (strs.empty() == 1)
return “”;
prefix = strs[0];
for (vector<string>::iterator it = (strs.begin() + 1); it != strs.end(); ++it) {
if (prefix.compare(*it) != 0) {
int index = 0;
int sizePrefix = prefix.size();
int sizeCompare = (*it).size();
int size = (sizePrefix < sizeCompare) ? sizePrefix : sizeCompare;
string oringin = prefix;
string toCompare = *it;
prefix.clear();
for (index = 0; index < size; index++) {
if (oringin[index] != toCompare[index])
break;
}
prefix.append(toCompare, 0, index);
}
}
return prefix;
}
};
網路上解答:
發現有兩個想法不錯:
(1) 先抓出第一個char ,比對整個陣列,若每個字串都有,再比對第二個char。
(2) 之前比較的方式是有個基準點,每個字串和他比較。可以換成兩兩互相比較,像是 divide and conquer的方式,可能不會比較快啦,程式碼架構可以改變的方式。
其他小細節像是找出最短的字串,以他為基礎開始比較,可以少一些運算,但是我不確定會不會真的有比較好,因為這相當於要多跑一次整個陣列,如果陣列很大,可能會有一些 cache miss。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string prefix = “”;
for(int idx=0; strs.size()>0; prefix+=strs[0][idx], idx++)
for(int i=0; i<strs.size(); i++)
if(idx >= strs[i].size() ||(i > 0 && strs[i][idx] != strs[i-1][idx]))
return prefix;
return prefix;
}
};
