Leetcode 14. Longest Common Prefix

Longest Common Prefix

Longest Common Prefix :

從一組字串陣列中找出其最長的共用前綴,沒有的話則回傳空字串。

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++

  1. 比對前兩個字串,從頭開始取出相同的部分為共同字首
  2. 後面的字串只要與目前的共同字首比對即可
  3. [‘abcd’,’abccc’,’abdec’] ,一開始’abcd’,’abccc’共同字首前3碼’abc’
  4. 接下來只要將’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;
  }
};