Coding problem · Easy · Basics

Longest Common Prefix

Easy Algorithms & data structures

Given a list of words, return the longest common prefix they all start with, or "" if there isn't one.

Example 1

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

Example 2

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

Hints

Hint 1

Start with the first word as the prefix.

Hint 2

Shorten it until every other word starts with it.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n·m) · Space O(1)

Take the first word as a candidate and trim characters from its end while any word doesn't start with it. Or compare column by column until a mismatch.

Reference solution

function longestCommonPrefix(words) {
  let prefix = words[0];
  for (const w of words) while (!w.startsWith(prefix)) prefix = prefix.slice(0, -1);
  return prefix;
}

function longestCommonPrefix(words: string[]): string {
  let prefix = words[0];
  for (const w of words) while (!w.startsWith(prefix)) prefix = prefix.slice(0, -1);
  return prefix;
}

def longest_common_prefix(words: list[str]) -> str:
    prefix = words[0]
    for w in words:
        while not w.startswith(prefix):
            prefix = prefix[:-1]
    return prefix

<?php

function longestCommonPrefix(array $words): string
{
    $prefix = $words[0];
    foreach ($words as $w) {
        while (!str_starts_with($w, $prefix)) {
            $prefix = substr($prefix, 0, -1);
        }
    }
    return $prefix;
}

class Solution {
    public String longestCommonPrefix(String[] words) {
        String prefix = words[0];
        for (String w : words) while (!w.startsWith(prefix)) prefix = prefix.substring(0, prefix.length() - 1);
        return prefix;
    }
}

Was this page helpful?