14. Longest Common Prefix

Question

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"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters if it is non-empty.

Prakash Sellathurai · Accepted Answer

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # 
        # 1. Find the shortest string length (this is your loop limit)
# 2. For each position from 0 to shortest_length:
#    - Compare character at that position across ALL strings
#    - If any mismatch or out of bounds: STOP and return prefix so far
#    - Otherwise: add this character to the result
# 3. Return the result
#  
        if not strs:
            return ""

min_len = min(len(s) for s in strs)
        prefix = ""

for pos in range(min_len):
            char = strs[0][pos]
            for s in strs[1:]:
                if s[pos] != char:
                    return prefix
            prefix += char
        return prefix