easyStringsPattern: Two Pointers
Longest Common Prefix String Solution
Problem Statement
Given an array of strings `strs`, find the longest common prefix string amongst all strings in the array. If there is no common prefix, return an empty string "".
Examples
Example 1:
Input:["flower","flow","flight"]
Output:"fl"
Explanation: The longest common prefix of the list of strings ["flower", "flow", "flight"] is "fl".
Example 2:
Input:["dog","racecar","car"]
Output:""
Explanation: There is no common prefix among the input strings ["dog", "racecar", "car"]. Therefore, an empty string is returned.
Example 3:
Input:["apple"]
Output:"apple"
Explanation: When there's only one string in the list, it is its own longest common prefix.
Example 4:
Input:["cir","car"]
Output:"c"
Explanation: The longest common prefix of the list of strings ["cir", "car"] is "c".
Constraints
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] consists of only lowercase English letters.
- All the strings of strs are unique if strs.length > 0.
Time: O(S) Space: O(1)
Start with the first string as the potential prefix. Iterate through the rest of the strings, comparing characters from the beginning. Shorten the potential prefix if a mismatch is found or if the current string is shorter.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def longest_common_prefix(strs):
if not strs:
return ""
shortest_str = min(strs, key=len)
for i, char in enumerate(shortest_str):
for other_str in strs:
if other_str[i] != char:
return shortest_str[:i]
return shortest_str