Solutions

1. Character by Character

O(n * m) time | O(1) space, for n strings of length m

Intuition

We can compare the strings with each other character by character.

The prefix ends when some string has a different character or has no character at all.

Algorithm

Iterate through the outer loop from the first character to the last character of the first string with i index.
For each outer loop iteration, iterate through the inner loop from the first string to the last string.
If the string ends at i or its character at i differs from the character of the first string, return the first i characters of the first string.
Return the first string when both loops finish.

012345

f = f

1 / 7

Code

def longestCommonPrefix(strs: list[str]) -> str:
    first = strs[0]
    for i in range(len(first)):
        for word in strs:
            if i == len(word) or word[i] != first[i]:
                return first[:i]
    return first

/**
 * @param {string[]} strs
 * @returns {string}
 */
var longestCommonPrefix = function (strs) {
  const first = strs[0]
  for (let i = 0; i < first.length; i++) {
    for (const word of strs) {
      if (i === word.length || word[i] !== first[i]) return first.slice(0, i)
    }
  }
  return first
}

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String first = strs[0];
        for (int i = 0; i < first.length(); i++) {
            for (String word : strs) {
                if (i == word.length() || word.charAt(i) != first.charAt(i)) return first.substring(0, i);
            }
        }
        return first;
    }
}