Longest Common Prefix
Find the longest common prefix among all strings — vertical scan or trie walk.
3 min read
strings
Problem#
Given an array of strings, return the longest common prefix shared by all of them. Return "" if there is none.
Examples#
["flower","flow","flight"]→"fl".["dog","racecar","car"]→"".
Constraints#
1 <= strs.length <= 200,0 <= strs[i].length <= 200.
Hints#
Hint
Scan column by column; bail at the first mismatch or when a string ends.
Approach#
Vertical scan. At index i, compare every string’s i-th character against strs[0][i]. If any string is shorter than i or differs, return strs[0].substr(0, i).
Solution#
class Solution {public: string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; for (int i = 0; i < (int)strs[0].size(); ++i) { char c = strs[0][i]; for (int j = 1; j < (int)strs.size(); ++j) { if (i >= (int)strs[j].size() || strs[j][i] != c) return strs[0].substr(0, i); } } return strs[0]; }};func longestCommonPrefix(strs []string) string { if len(strs) == 0 { return "" } for i := 0; i < len(strs[0]); i++ { c := strs[0][i] for j := 1; j < len(strs); j++ { if i >= len(strs[j]) || strs[j][i] != c { return strs[0][:i] } } } return strs[0]}from typing import List
class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if not strs: return "" for i in range(len(strs[0])): c = strs[0][i] for j in range(1, len(strs)): if i >= len(strs[j]) or strs[j][i] != c: return strs[0][:i] return strs[0]function longestCommonPrefix(strs) { if (strs.length === 0) return ""; for (let i = 0; i < strs[0].length; i++) { const c = strs[0][i]; for (let j = 1; j < strs.length; j++) { if (i >= strs[j].length || strs[j][i] !== c) { return strs[0].slice(0, i); } } } return strs[0];}class Solution { public String longestCommonPrefix(String[] strs) { if (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]; }}function longestCommonPrefix(strs: string[]): string { if (strs.length === 0) return ""; for (let i = 0; i < strs[0].length; i++) { const c = strs[0][i]; for (let j = 1; j < strs.length; j++) { if (i >= strs[j].length || strs[j][i] !== c) { return strs[0].slice(0, i); } } } return strs[0];}Editorial#
Vertical scan terminates as soon as one column disagrees, so total work is O(min_len * N) — much better than building a trie when the prefix is short. The trie alternative is conceptually cleaner but overkill for this size.
Complexity#
- Time: O(S) where S is total characters in the prefix range.
- Space: O(1).
Concept revision#
Related#