iTechGuides is reader-supported. When you buy through links on our site, we may earn an affiliate commission. As an Amazon Associate I earn from qualifying purchases. Learn more
Compare the strings from left to right and stop at the first position where any string ends or differs. The characters before that position are the longest common prefix; if the first position fails, return "".
What counts as a common prefix?
A prefix is a sequence of characters shared from the beginning of every string. It is not a substring that can appear somewhere else in the strings. For example, flower, flow, and flight share the prefix fl. The strings dog, racecar, and car share no prefix, so the result is "". LeetCode’s problem statement allows 1 to 200 strings, each 0 to 200 characters long; non-empty strings contain lowercase English letters.
Compare characters by position
Use the first string as a reference and scan it from left to right. At each position, compare its character with the character at the same position in every other string.
The Tool Desk
Outbyte PC Repair FREERepair Windows errors before they cause bigger problemsFix Now →Outbyte Driver Updater FREEScan for outdated or missing drivers - takes under a minuteDriver Scan →- If any other string has ended, the shared prefix stops before this position.
- If any character differs from the reference character, the shared prefix stops before this position.
- If every string matches, continue to the next position.
Return the part of the first string before the first failed position. If the scan reaches the end of the first string without a failure, return the whole first string. A mismatch or an ended string ends the prefix permanently: later characters cannot make the earlier positions match.
#1 Best Overall
Python implementation
def longest_common_prefix(strs: list[str]) -> str:
first = strs[0]
for i, char in enumerate(first):
for word in strs[1:]:
if i == len(word) or word[i] != char:
return first[:i]
return firstThe length check comes before word[i] so the code never indexes past the end of a shorter string. The stated constraints guarantee at least one input string, so strs[0] is available. An empty first string skips the loop and returns ""; an empty later string triggers the length check at the first position and also returns "".
Complexity and why this approach fits
Let n be the number of strings and m the length of the shortest string. The character-comparison method takes O(n × m) time in the worst case and O(1) auxiliary space, excluding the returned prefix string. The scan may stop earlier when it finds a mismatch. The slice used to return the prefix can allocate the output string.
A trie is another possible approach, but the direct scan is easier to implement for the problem’s stated bounds and needs no extra data structure. The cited solution explains the direct method’s complexity but does not provide measured runtime comparisons with a trie.
Check the result with examples
["flower", "flow", "flight"]returns"fl": the first two positions match across all strings, and the next position differs.["dog", "racecar", "car"]returns"": the first characters already differ.["abc", "ab"]returns"ab": the second string ends after the shared characters.["", "abc"]returns"": an empty string cannot share a non-empty prefix.
For the official statement and examples, see LeetCode’s Longest Common Prefix problem. The character-by-character solution and complexity analysis are also described in the Doocs LeetCode Wiki explanation.
Quick Recap
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
