旭的小窝

14. Longest Common Prefix

 
  • 2023年 06月16日

Promble

link: https://leetcode.com/problems/longest-common-prefix/description/

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 “”.

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

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Approach 1

Thought

  1. def ans:str to store the final result
  2. sort the strs, because we only compare the first and last str
  3. num:int is the min length in strs
  4. def first:str and last:str
  5. loop i in range(num)
    1. if (first[i] != last[i]): return ans
    2. ans+=first[i]
  6. return ans

Code

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ans = ""
        strs = sorted(strs)
        num = min([len(i) for i in strs])
        first = strs[0]
        last = strs[-1]

        for i in range(num):
            if (first[i] != last[i]):
                return ans 

            ans += first[i]

        return ans

Approach 2

Thought

  1. judge the len(strs) <= 1.
  2. def end, minl is 0 and min(len(strs))
  3. while end<minl
    1. loop i in range(1, len(strs))
      1. if strs[i][end] != strs[i-1][end]: return strs[0][:end]
    2. end += 1
  4. return strs[0][:end]

Code

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) <= 1:
            return strs[0] if len(strs) == 1 else ""

        end, minl = 0, min([len(s) for s in strs])
        while end<minl:
            for i in range(1, len(strs)):
                if strs[i][end] != strs[i-1][end]:
                    return strs[0][:end]

            end = end + 1

        return strs[0][:end]
搜索