14.Longest_Common_Prefix(Easy).md

14. Longest Common Prefix (Easy)

Date and Time: Jul 7, 2024, 17:16 (EST)

Link: https://leetcode.com/problems/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.

Self-added case 1:

Input: strs = ["flow", "fl"]

Output: "fl"

Self-added case 2:

Input: strs = ["flow"]

Output: "flow"

Constraints:

• 1 <= strs.length <= 200

• 0 <= strs[i].length <= 200

• strs[i] consists of only lowercase English letters.

KeyPoints:

The way to solve it is to pick a random string (strs[0]) to start with, then we compare it with all the str in strs character by character, if a len(str) == i, which is the ith index of a str, or str[i] != strs[0][i] means there is no match for word in a str, we should return the current res; otherwise, we should update the res.

My Solution:

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # Randomly pick one str then compare with other strs one by one
        res = ""
        for i in range(len(strs[0])):
            for str in strs:
                if len(str) == i or str[i] != strs[0][i]:
                    return res
            res += str[i]
        return res

Time Complexity: $O(n)$
Space Complexity: $O(n)$