Leetcode No.3( Longest Common Prefix) 心得

ChingYuanYang
Aug 23, 2017 · 1 min read

題目:
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;
}
};

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade