Longest common prefix

Easy TimeO(n·m) SpaceO(1)

Given an array of strings words, return the longest run of characters that every one of them starts with, or the empty string "" when they share none. The run has to begin at the first character of each string, so the shortest string in the array bounds how long it can be. An empty array, or an empty string anywhere in it, makes the answer empty.

Examples

Example 1

Input
words = ["flower", "flow", "flight"]
Output
"fl"
All three open with f and then l; at the third character "flight" has i where the others have o.

Example 2

Input
words = ["dog", "racecar", "car"]
Output
""
The three disagree on their very first character, so there is nothing to share.

The Code

function longestCommonPrefix(words) {
  if (words.length === 0) return "";
  let prefix = words[0];
  for (let i = 1; i < words.length; i++) {
    while (!words[i].startsWith(prefix)) {
      prefix = prefix.slice(0, prefix.length - 1);
      if (prefix === "") return "";
    }
  }
  return prefix;
}
longestCommonPrefix(["flower", "flow", "flight"]);
Done
Step through longestCommonPrefix(["flower", "flow", "flight"]) call by call

More like this

All strings examples (13) →