10.3 Longest Common Prefix

10.3.1 Problem Metadata

10.3.2 Description

Given an array of strings, return the longest common prefix string among them. If none exists, return "".

10.3.3 Examples

Input: ["flower","flow","flight"]
Output: "fl"

Input: ["dog","racecar","car"]
Output: ""

10.3.4 Constraints

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200

10.3.5 Solution - Column Scan

10.3.5.1 Walkthrough

Use the first string as a baseline. For each character index, ensure all other strings have the same character. Stop once a mismatch or end of string occurs.

10.3.5.2 Analysis

  • Time Complexity: O(n * m), n strings and m average length
  • Space Complexity: O(1)

10.3.5.3 Implementation Steps

  1. Handle empty input.
  2. Iterate index i across the first string.
  3. For each i, compare strs[j].charAt(i) with strs[0].charAt(i); return strs[0].substring(0, i) on mismatch.
  4. If no mismatch, return the entire first string.

10.3.5.4 Code - Java

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    for (int i = 0; i < strs[0].length(); i++) {
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j++) {
            if (i == strs[j].length() || strs[j].charAt(i) != c) {
                return strs[0].substring(0, i);
            }
        }
    }
    return strs[0];
}