Longest Common Prefix
The key idea
Scan the strings vertically, one character column at a time. For each column index, check that every string shares the same character there; the first column where any string disagrees or runs out of characters ends the common prefix. The answer can never be longer than the shortest input string.
Problem
Write a function to find the longest common prefix string amongst an array of strings strs.
The common prefix is the longest run of characters, starting from index 0, that every string in the array shares. If there is no common prefix, return the empty string "".
Constraints
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]consists of only lowercase English letters.
Examples
Input: strs = ["flower","flow","flight"]
Output: "fl"
Input: strs = ["dog","racecar","car"]
Output: ""
Input: strs = ["ab","abc","abd"]
Output: "ab"
Complexity
Time: O(S) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization