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

Example 1:

Input:"flower"."flow"."flight"] output:"fl"
Copy the code

Example 2:

Input:"dog"."racecar"."car"] output:""Explanation: The input does not have a common prefix.Copy the code

Description:

All inputs contain only lowercase letters A-z.

Solution one: compare one by one

Compare strings from front to back to get the common prefix

Draw a picture to help understand:

Code implementation:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    let prevs = strs[0]
    for(let i = 1; i < strs.length; i++) {
        let j = 0
        for(; j < prevs.length && j < strs[i].length; j++) {
            if(prevs.charAt(j) ! == strs[i].charAt(j))break
        }
        prevs = prevs.substring(0, j)
        if(prevs === "") return ""
    }
    return prevs
};
Copy the code

Time complexity: O(s), where S is the sum of the number of characters in all strings

Space complexity: O(1)

Solution 2: Only the longest common prefix for the largest and smallest strings

The longest public prefix of the smallest and largest strings is also the public prefix of other strings, that is, the longest public prefix of the string array

B > A, AC > AB, ac > ABC. Check in the browser console

For example, ABC, abcd, ab, and AC, the longest public prefix of minimum AB and maximum AC must also be the public prefix of ABC and ABcd

Draw a picture to help understand:

Code implementation:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    if(strs.length === 1) return strs[0]
    let min = 0, max = 0
    for(let i = 1; i < strs.length; i++) {
        if(strs[min] > strs[i]) min = i
        if(strs[max] < strs[i]) max = i
    }
    for(let j = 0; j < strs[min].length; j++) {
        if(strs[min].charAt(j) ! == strs[max].charAt(j)) {return strs[min].substring(0, j)
        }
    }
    return strs[min]
};
Copy the code

Time complexity: O(n+m), where n is the length of the array and M is the length of the shortest character in the string array

Space complexity: O(1)

Solution three: divide and conquer strategy merge thought

Divide and conquer, as the name implies, is divide and conquer, divide a complex problem into two or more similar sub-problems, then divide the sub-problems into smaller sub-problems, until the smaller sub-problems can be solved simply, solve the sub-problems, then the solution of the original problem is the combination of the sub-problems.

This is a classic divide-and-conquer problem:

  • Problem: Find the longest common prefix for multiple strings
  • Decomposed into similar subproblems: Find the longest common prefix of two strings
  • The subproblem can be solved simply: the longest common prefix of two strings is easy to solve
  • The solution of the original problem is the combination of the sub-problem: the longest common prefix of multiple strings is the longest common prefix of two strings. We can merge and compare the longest common prefix of two strings until the final merge and compare is the longest common prefix of string array:LCP(S1, S2, ... , Sn) = LCP(LCP(S1, Sk), LCP(Sk+1, Sn))

Draw a picture to help understand:

For example, ABC, ABCD, AB, and AC:

Code implementation:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    return lCPrefixRec(strs)
};

// If the length of the two arrays is not 1, continue to split
// Until the array is split, the length is 1.
// Then compare to get the longest public prefix
function lCPrefixRec(arr) {
  let length = arr.length
  if(length === 1) {
    return arr[0]}let mid = Math.floor(length / 2),
      left = arr.slice(0, mid),
      right = arr.slice(mid, length)
  return lCPrefixTwo(lCPrefixRec(left), lCPrefixRec(right))
}

// find the longest common prefix str1 and str2
function lCPrefixTwo(str1, str2) {
    let j = 0
    for(; j < str1.length && j < str2.length; j++) {
        if(str1.charAt(j) ! == str2.charAt(j)) {break}}return str1.substring(0, j)
}
Copy the code

Time complexity: O(s), where S is the sum of the number of characters in all strings

Space complexity: O(m*logn), where n is the length of the array and M is the length of the longest character in the string array

Solution 4: Trie tree (dictionary tree)

A Trie tree, also known as a dictionary tree or prefix tree, is, as the name suggests, a data structure for dealing with string matching problems, as well as for solving the problem of looking up fixed prefix strings in collections.

Construct a Trie tree where the longest common sequence of strings is to traverse the tree from the root node until:

  • Traversal nodes nodes that have more than one child node

  • Or the traversal node is the end character of a string

Up to the longest public prefix of the string array

Draw a picture to help understand:

Construct a Trie tree using ABC, ABcd, ab, ac as examples:

Code implementation:

var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    // Initialize the Trie tree
    let trie = new Trie()
    // Build the Trie tree
    for(let i = 0; i < strs.length; i++) {
        if(! trie.insert(strs[i]))return ""
    }
    // Returns the longest public prefix
    return trie.searchLongestPrefix()
};
/ / Trie tree
var Trie = function() {
    this.root = new TrieNode()
};
var TrieNode = function() {
    // next Puts the child node of the current node
    this.next = {};
    // Is the end node
    this.isEnd = false;
};
Trie.prototype.insert = function(word) {
    if(! word)return false
    let node = this.root
    for (let i = 0; i < word.length; i++) {
        if(! node.next[word[i]]) { node.next[word[i]] =new TrieNode()
        }
        node = node.next[word[i]]
    }
    node.isEnd = true
    return true
};
Trie.prototype.searchLongestPrefix = function() {
    let node = this.root
    let prevs = ' '
    while(node.next) {
        let keys = Object.keys(node.next)
        if(keys.length ! = =1) break
        if(node.next[keys[0]].isEnd) {
            prevs += keys[0]
            break
        }
        prevs += keys[0]
        node = node.next[keys[0]]}return prevs
}
Copy the code

Time complexity: O(s+m), s is the sum of the number of characters in all strings, m is the length of the longest character in the string array, O(s) is required to build the Trie tree, and the complexity of the longest public prefix query operation is O(m).

Spatial complexity: O(s) for building Trie trees

The last

Welcome to pay attention to “front-end bottle Gentleman”, reply to “communication” to join the front-end communication group!

Welcome to pay attention to “front-end bottle gentleman”, reply to “algorithm” automatically join, from 0 to 1 to build a complete data structure and algorithm system!

Here, I not only introduce algorithms, but also combine algorithms with various front-end areas, including browsers, HTTP, V8, React, Vue source code, and so on.

Here (algorithm group), you can learn a dachang algorithm programming problem (Ali, Tencent, Baidu, Byte, etc.) or Leetcode every day, Mr. Aquarius will solve it the next day!

In addition, there are handwritten source code problems every week, Aquarius will also solve!