[leetcode] 14. Longest Common Prefix

Table of Contents

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 "".

Example 1:

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

Example 2:

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

Constraints:

• $1 \leq \text{strs.length} \leq 200$
• $0 \leq \text{strs[i].length} \leq 200$
• $\text{strs[i]}$ consists of only lowercase English letters.

Approach

We iterate through each character index of the first string. For each character at the current index, we check if it is present in all strings at the same index. If any string does not match, we break out of the loop. Otherwise, we add the character to the common prefix.

Solution

/**
 * Finds the longest common prefix among an array of strings.
 *
 * @param {string[]} strs - The input array of strings.
 * @return {string} - The longest common prefix shared by all strings.
 */
var longestCommonPrefix = function (strs) {
  // Initialize the common prefix as an empty string.
  let commonPrefix = "";

  // Loop through each character index of the first string.
  for (let i = 0; i < strs[0].length; i++) {
    // Get the character at the current index in the first string.
    let c = strs[0][i];

    // Check if the character at position i in all strings is equal to c.
    // If any string does not match, break out of the loop.
    if (!strs.every(str => str[i] === c)) break;

    // If the character matches in all strings, add it to the common prefix.
    commonPrefix += c;
  }

  return commonPrefix;
};

Complexity Analysis

Time Complexity

The time complexity is $O(n \times m)$, where $n$ is the number of strings in the input array strs, and $m$ is the length of the first string in the array. We iterate through each character index of the first string and compare it with the corresponding characters in the other strings.

Space Complexity

The space complexity is $O(m)$, where $m$ is the length of the first string in the input array. We store the common prefix string, which can be at most the length of the first string.