This article is participating in Python Theme Month. See the link for details

review

  • A brush: juejin. Cn/post / 698914…
  • Two brush: juejin. Cn/post / 698944…
  • Three brush: juejin. Cn/post / 699017…

describe

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 1:

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

Example 2:

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

Note:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lower-case English letters.
Copy the code

parsing

Before several solution methods, we used the method of horizontal and vertical scanning method, the binary search method, the built-in function method, this time we use a new solution, by using the method of divide and conquer, understand the title carefully, we found that if you want to find the longest common prefix string LCP, then assume that the final result for the variable result, The number of strings in the STRS list is n, then

  • result = LCP(S0, Sn-1) = LCP(LCP(S0, Sk(S), LCPk+1, Sn-1))

This formula can go on and on and on, infinite nesting dolls. By observing the divide-and-conquer formula above, we can actually see that the result of any sublist can be converted to the following form:

  • LCP(Si, Sj) = LCP(LCP(Si, Smid(S), LCPmid+1, Sj), where mid is (I +j)//2

This is the idea of divide-and-conquer by breaking up a big problem into many of the same small problems, where we can break down the STRS into one-to-one pairs of strings, and then combine the LCP from each pair of strings upward until all the answers are combined into one LCP. Therefore, we define a divide function to continuously divide STRS into pairs of string pairs, and LCP function to solve the longest common prefix of two strings.

The results show that divide and conquer is slow and takes up a lot of memory.

answer

class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ def LCP(a, b): index = 0 for i in range(min(len(a), len(b))): if a[i] ! = b[i]: break index += 1 return a[:index] def divide(strs, l, r): if l == r: return strs[l] m = (l + r) // 2 a = divide(strs, l, m) b = divide(strs, m + 1, r) return LCP(a, b) if not strs: return "" return divide(strs, 0, len(strs) - 1)Copy the code

The results

The node is linked to the node in the linked list. Memory Usage: The Longest Common Prefix is linked to the Python online submissions.Copy the code

Original link: leetcode.com/problems/lo…

Your support is my biggest motivation