0014-longest-common-prefix

Try it on leetcode

Description

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.

Solution(Python)

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