Longest Common Prefix Easy 0 attempts
LeetCode ↗

Longest Common Prefix

Easy StringHash Table LeetCode

You're given an array of strings. Work out the longest prefix that every single one of them starts with. If the strings don't share any starting characters at all, return an empty string "".

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

Input Format
Implement longestCommonPrefix(strs). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

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

Approach: Horizontal Scan

Take the first string as the initial prefix. Compare it against each subsequent string, comparing corresponding characters to find the matching prefix length. If the prefix ever becomes empty, short-circuit and return "".

javascript
function longestCommonPrefix(strs) {
  if (!strs.length) return '';
  let length = strs[0].length;
  for (let i = 1; i < strs.length; i++) {
    let j = 0;
    while (j < length && j < strs[i].length && strs[0][j] === strs[i][j]) j++;
    length = j;
    if (length === 0) return '';
  }
  return strs[0].slice(0, length);
}

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

Space Complexity: O(p) for the returned prefix, O(1) auxiliary space

Saved in this browser only. Private to you.

JavaScript