Leetcode：14. Longest common prefix [thinking + sorting]

Title Description

Write a function to find the longest common prefix in the string array .
If no common prefix exists , Returns an empty string “”.

Input and output

Input ：strs = [“flower”,“flow”,“flight”]
Output ：“fl”

Input ：strs = [“dog”,“racecar”,“car”]
Output ：""
explain ： Input does not have a common prefix .

Tips

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] It's only made up of lowercase letters

Ideas

If we can sort strings , Then we only need to judge the public prefix of the first string and the last string , Because the longest common prefix depends on the first string and the last string , And the middle string will not affect .

AC Code （C++）

class Solution {
    
public:
    string longestCommonPrefix(vector<string>& strs) {
    
        sort(strs.begin(), strs.end());
        string first = strs.front();
        string end = strs.back();
        string res = "";
        for (int i = 0; i < first.size() && i < end.size(); ++i) {
    
            if (first[i] != end[i]) {
    
                break;
            }
            res += first[i];
        }
        return res;
    }
};

AC Code （Java）

class Solution {
    
    public String longestCommonPrefix(String[] strs) {
    
        Arrays.sort(strs);
        String first = strs[0];
        String end = strs[strs.length - 1];
        String res = "";
        for (int i = 0; i < first.length() && i < end.length(); ++i) {
    
            if (first.charAt(i) != end.charAt(i)) {
    
                break;
            }
            res += first.charAt(i);
        }
        return res;
    }
    //Array.sort（strs） Is the default sort , You can choose a sorting interval .
}

AC Code （Python）

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs.sort()
        first, end = strs[0], strs[-1]
        i, res = 0, ""
        while i < len(first) and i < len(end):
            if first[i] != end[i]:
                break
            else:
                res += first[i]
                i += 1
        return res
   //strs.sort() Sort the original list , The original table has changed , and sorted(strs) The function returns an object .