easyStringsPattern: Two Pointers
LongestCommonPrefixLength Solution
Problem Statement
Given two strings `str1` and `str2`, find the length of the longest common prefix between them.
Examples
Example 1:
Input:{'str1': 'flower', 'str2': 'flowe'}
Output:
Explanation: The longest common prefix between 'flower' and 'flowe' is 'flowe', which has a length of 5.
Example 2:
Input:{'str1': 'apple', 'str2': 'apply'}
Output:
Explanation: The longest common prefix between 'apple' and 'apply' is 'appl', which has a length of 3.
Example 3:
Input:{'str1': 'aaa', 'str2': 'abba'}
Output:
Explanation: The longest common prefix between 'aaa' and 'abba' is 'aa', which has a length of 2.
Constraints
- Both `str1` and `str2` are non-empty strings.
- The input strings can contain uppercase or lowercase letters.
- The input strings can contain repeated characters.
Time: O(min(len(str1), len(str2))) Space: O(1)
You can use a single pass through the strings to find the length of the longest common prefix, with a time complexity of O(min(len(str1), len(str2))).
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 ''
prefix = ''
shortest = min(strs, key=len)
for i, char in enumerate(shortest):
if char == strs[0][i]:
prefix += char
else:
break
return prefix