Longest Common Prefix Easy 0 attempts
LeetCode ↗

Longest Common Prefix

Easy StringHash Table LeetCode

Given an array of strings, find the longest common prefix shared by all of them. 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: No common prefix exists.

Edge cases: Array with a single string returns that string. Empty array returns "". One of the strings is empty.

Sample Input
strs = ["flower","flow","flight"]
Sample Output
"fl"
Constraints
  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of lowercase English letters
Test Cases
Case 1
Args: [["flower","flow","flight"]] Expected: "fl"
Topics
StringHash Table

Approach: Horizontal Scan

Take the first string as the initial prefix. Compare it against each subsequent string, trimming from the end until it matches the beginning of that string. If the prefix ever becomes empty, short-circuit and return "".

function longestCommonPrefix(strs) {
  if (!strs.length) return '';
  let prefix = strs[0];

  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.slice(0, -1);
      if (!prefix) return '';
    }
  }
  return prefix;
}

Time Complexity: O(S) where S is the total number of characters across all strings

Space Complexity: O(1)

Saved in this browser only. Private to you.

JavaScript