Longest Common Prefix

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Find the longest common prefix amongst given list of strings

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Minimum length of word amongst all word is the maximum a prefix could be

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Array
• Strings

Time & Space Complexity

• Time: $O(numofwords+averagelengthofaword)$ → Reason:
• Space: $O(1)$ → Reason: Storing one word which is the longest common prefix

Code

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1:
            return strs[0]

        minLength = inf
        for word in strs:
            minLength = min(minLength, len(word))

        result = []

        i = 0
        while i < minLength:
            for word in strs:
                if word[i] != strs[0][i]:
                    return "".join(result)
            result.append(word[i])
            i += 1
        return "".join(result)

Common Mistakes / Things I Got Stuck On

• Looping with for and while together
• Over thinking the solution