Skip to content

LeetCode: 14-Longest Common Prefix 解題紀錄

Last Updated on 2021-01-07 by Clay

題目

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Input: strs = ["dog","racecar","car"]
Output: ""

題目給定一陣列，裡頭存放許多組字串，而我們要做的就是找到他們共同的前綴字串並回傳；若無共同的前綴，則回傳空字串 “”。

解題思路

這題我使用了比較暴力的方法直接做比對。


C++ 程式碼

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        // Preventation
        if (strs.empty()) return "";
        if (strs.size() == 1) return strs[0];
        
        // Init
        string ans = "";
        int min_len = 200;
        
        for (string str: strs) {
            if (str.size() < min_len) {
                min_len = str.size();
            }
        }
                
        // Comparison
        for (int i=0; i<min_len; i++) {
            for (int si=0; si<strs.size()-1; si++) {
                if (strs[si][i] != strs[si+1][i]) {
                    return ans;
                }                
            }
            
            ans += strs[0][i];
        }
        
        return ans;
    }
};


Python 程式碼

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # Preventation
        if not strs: return ''
        if len(strs) == 1: return strs[0]
        
        # Init
        ans = ""
        min_len = 200
        
        for s in strs:
            if len(s) < min_len:
                min_len = len(s)
        
        # Comparison
        for i in range(min_len):
            for si in range(len(strs)-1):
                if (strs[si][i] != strs[si+1][i]):
                    return ans
            
            ans += strs[si][i]
        
        return ans


References

Tags:

Leave a Reply