This is another good one, I think. Strings and arrays are commonly-requested topics.
- We can observe that “the first string must contain the longest common prefix”. That’s an interesting tool that we can leverage.
- So we know that we can iterate over that length. We want to “scan” all the strings in parallel, and that’s how.
- We have an interesting “return from a nested loop” potential. Helper functions may make this clearer. Potential sequel homework.
class Solution(object):
def longestCommonPrefix(self, strs):
if len(strs) == 0:
return ""
root = strs[0]
if len(root) == 0:
return ""
prefixLen = 0
for i in range(len(root)):
for s in strs[1:]:
if i >= len(s):
return root[:prefixLen]
if s[i] != root[i]:
return root[:prefixLen]
prefixLen += 1
return root