Day 27 : Longest Common Prefix : leetcode :python3

 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.

SOLUTION

class Solution:

    def longestCommonPrefix(self, strs: List[str]) ->str:

        result: str=""

        for j in range(len(strs[0])):

            for i in range(1,len(strs)):

                if j >= len(strs[i]) or strs[i][j] !=strs[0][j]:

                    return result

            result += strs[0][j]

        return result

Time Complexity: O(n)

Space Complexity:O(1)

How it works:

• First, the code creates a variable called result that will store the longest common prefix.
• Next, the code loops through the string strs[0], character by character. For each character, the code checks if the same character exists in all of the other strings in strs.
• If the character does not exist in all of the other strings, the code returns result. This is because the current character cannot be part of the longest common prefix.
• If the character does exist in all of the other strings, the code adds the character to result.
• The code continues looping until it reaches the end of the string strs[0].
• Finally, the code returns result. This is the longest common prefix of all of the strings in strs.