This is the 15th day of my participation in the genwen Challenge

Topic describes

Write a function to find the longest public prefix in an array of strings.

Returns the empty string “” if no public prefix exists.

Example 1:

STRS = ["flower","flow","flight"]Copy the code

Example 2:

Input: STRS = ["dog","racecar","car"] Output: "" Explanation: The input does not have a common prefix.Copy the code

Tip:

  • 0 < =strs.length< = 200
  • 0 < =strs[i].length< = 200
  • strs[i]Contains only lowercase English letters

Their thinking

Solution 1: Python feature, take each word in the same position of the letter, see if the same

class Solution:
    def longestCommonPrefix(self, strs) :
        """ :type strs: List[str] :rtype: str """
        res = ""
        for tmp in zip(*strs):
            tmp_set = set(tmp)
            if len(tmp_set) == 1:
                res += tmp[0]
            else:
                break
        return res
Copy the code

Solution two: take a word s and compare it with the next word to see how long s has the same prefix as each word. Walk through all the words.

class Solution:
    def longestCommonPrefix(self, s: List[str]) - >str:
        if not s:
            return ""
        res = s[0]
        i = 1
        while i < len(s):
            whiles[i].find(res) ! =0:
                res = res[0:len(res)-1]
            i += 1
        return res
Copy the code

Solution three sort the array lexicographically and compare how many prefixes the first and last word have the same

class Solution:
    def longestCommonPrefix(self, s: List[str]) - >str:
        if not s:
            return ""
        s.sort()
        n = len(s)
        a = s[0]
        b = s[n-1]
        res = ""
        for i in range(len(a)):
            if i < len(b) and a[i] == b[i]:
                res += a[i]
            else:
                break
        return res
Copy the code

C++ version if no string, return empty string; If there is only one string, return it.

Otherwise, for each character of STRS [0], compare the rest of the string one by one. If it finds any that are not long enough, or that the characters do not match, it ends there and returns the substring that has been compared so far.

If all STRS [0] characters are compared, return itself.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() = =0)
            return "";
        if (strs.size() = =1)
            return strs[0];
        
        for (int length = 0; length < strs[0].size(a); ++length)for (int i = 1; i < strs.size(a); ++i)if (length == strs[i].size() || strs[i][length] ! = strs[0][length])
                    return strs[0].substr(0, length);
        return strs[0]; }};Copy the code