Problem Statement

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 “”.

Longest Common Prefix - LeetCode

Approach

  1. Iterate over the characters of the first string.
  2. For each character, add it to the commonPrefix and iterate over the strings in the array.
  3. If the string does not have the commonPrefix, remove the last character from the commonPrefix and return the commonPrefix.

Solution in Swift

class Solution {
    func longestCommonPrefix(_ strs: [String]) -> String {
        guard let first = strs.first else { return "" }
        var commonPrefix = ""
        
        for character in first {
            commonPrefix.append(character)
            for item in strs {
                if !item.hasPrefix(commonPrefix) {
                    return String(commonPrefix.dropLast(1))
                }
            }
        }
        
        return commonPrefix
    }
}

Complexity

  • Time complexity: \(O(n * m)\) where \(n\) is the number of strings and \(m\) is the length of the shortest string.
  • Space complexity: \(O(m)\), where \(m\) is the length of the shortest string.