從一組字串陣列中找出其最長的共用前綴,沒有的話則回傳空字串。
Python
解法 : 從第一個字串開始,一個一個跟後面的字串比較內容,如果相同則把相同位置相同的值記錄到ans裡面,如果一有不同則回傳之前紀錄的ans,比對時可能會超出其他字串的長度。
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
ans=''
for i in range(len(strs[0])):
for j in strs:
if i>len(j)-1: #超出其他字串的長度
return ans
if strs[0][i]!=j[i]: #不同回傳之前紀錄的ans
return ans
ans=ans+strs[0][i] #相同位置相同的值記錄到ans裡面
return ans
C++
- 比對前兩個字串,從頭開始取出相同的部分為共同字首
- 後面的字串只要與目前的共同字首比對即可
- [‘abcd’,’abccc’,’abdec’] ,一開始’abcd’,’abccc’共同字首前3碼’abc’
- 接下來只要將’abc’,’abdec’做比對,發現剩下’ab’,也就是最長的共同字首
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return "";
string ans;
for (int i = 0; i < strs[0].size(); ++i) {
for (const string& s : strs)
if (s.length() <= i || s[i] != strs[0][i]) return ans;
ans += strs[0][i];
}
return ans;
}
};