Longest Common Prefix

String Simulation

Problem

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 "".

For example:

Input: strs = ["flower","flow","flight"]
Output: "fl"

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

Solution

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        
        res = ""
        if len(strs) == 0:
            return ""
        
        for i in range(len(strs[0])): #getting the character
            for j in range(1, len(strs)): #looping through the other strings
                if i >= len(strs[j]) or strs[0][i] != strs[j][i]:
                    return res
            res+=strs[0][i]
        return(res)
                
        
#We are vertically scanning: comparing the ith
#letter of the first string with the ith letter of
the other strings

#Time: O(number of strings * length of short string)
#Space: O(1)