class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not strs: return "" res = strs for s in strs: # if res has shrinked to empty or encounter an empty string, return result immediately if s == "" or res == "": return "" # if res == s, skip to next string if res == s: continue # compare res and other string from index 0 startIndex = 0 # find the break point where the common prefix may shrink while startIndex < len(s) and startIndex < len(res) and s[startIndex] == res[startIndex]: startIndex += 1 # update the res res = res[0:startIndex] return res
We start to treat the first string as the "common prefix". Then we compare this "common prefix" with other strings, after each comparison, there are only two results:
- "common prefix" stays the same
- "common prefix" becomes shorter
No matter which result happens, it has no impact on the previous strings, so after we traversed all the strings in the array, we can get the final "common prefix".