There are many ways to compare strings in strs. I just used vertical scanning and horizontal scanning, because I think the other methods are more complexity and harder to understand. Both solution 1 and solution 2 are vertical scanning. I found solution 2 online. “while true”, “try”, and “except” are use in solution 2.
Solution 1
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs: return ""
for i in range(len(strs[0])):
for string in strs[1:]:
if len(string) <= i or strs[0][i] != string[i]:
return string[:i]
#return "" is not right when the length of strs is 1.
return strs[0]
Time complexity is O(n). Space complexity is O(1).
Solution 2
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs: return ""
ans = ""
i = 0
while True:
try:
s = set(string[i] for string in strs)
if len(s) == 1:
ans += s.pop()
i += 1
else: break
except: break
return ans
Time complexity is O(n). Space complexity is O(1).
Solution 3
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs: return ""
ans = strs[0]
for i in range(1, len(strs)):
for string in strs[1:]:
if len(string) < len(ans):
ans = ans[:len(string)]
j = 0
while j < len(ans):
if string[j] == ans[j]:
j += 1
else:
ans = strs[0][:j]
break
return ans
Time complexity is O(n). Space complexity is O(1).
步步发财 