Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Plain Text
복사
Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Plain Text
복사
Constraints:
•
1 <= strs.length <= 200
•
0 <= strs[i].length <= 200
•
strs[i] consists of only lowercase English letters if it is non-empty.
To better understand the problem, I first looked up what a common prefix string is. A common prefix string is a sequence of characters that are the same and appear at the same position (index) in each string.
In programming terms, the characters must match and be located at the same index across all strings.
For example, between flower and flow, there is a common part fl, so the longest common prefix string would be fl. However, between abc and zab, the characters ab appear in both strings, but since their positions are different, they cannot form a common prefix string.
Since a common prefix must have both the same characters and the same index positions, we can start from index 0 and compare the characters at that position across all given strings in order.
The comparison only needs to be performed up to the length of the shortest string in the list.
This is because any index beyond that length will not exist in some strings and therefore can no longer be part of the common prefix.
from typing import List
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# If empty list has been given, return ""
if not strs:
return ''
min_length = min(len(s) for s in strs)
i = 0
result = ''
while i < min_length:
tmp = []
for s in strs:
tmp.append(s[i])
if all(t == tmp[0] for t in tmp):
result += tmp[0]
else:
break
i += 1
return result
Python
복사
First, if an empty list is passed as the parameter, return '' immediately and end the process.
Otherwise, determine the length of the shortest string in the list and run the loop for that length. Inside the loop, compare the characters at the i-th index of each string, and only if they are all the same, add the character to result one by one.
Fortunately, all the test cases passed.
I submitted the answer, and it passed.