iOS Interview - Leetcode 14: Longest Common Prefix

April 26, 2024 • 3 min read • #swift, #interview, #leetcode

Primary idea: Sort the array and find the common prefix between the first and the last string
Time Complexity: O(n*log n)+O(m) where m is the size of minimum word in array and n is the number of strings in the input array
Space Complexity: O(1)

func longestCommonPrefix(_ strs: [String]) -> String {
    let size = strs.count

    // if size is 0, return empty string
    if size == 0 {
        return ""
    }

    // if size is 1, return the first string
    if size == 1 {
        return strs[0]
    }

    // sort the array of strings
    let sortedA = strs.sorted()

    // find the minimum length from first and last string
    let shortestStringLength = min(sortedA[0].count, sortedA[size-1].count)

    // Integrate from the begining to the end of the first and the last string
    // to find the common prefix between the first and last string
    var i = 0
    while i < shortestStringLength && sortedA[0].prefix(i+1) == sortedA[size-1].prefix(i+1) {
        i += 1
    }

    let pre = String(sortedA[0].prefix(i))
    return pre
}

print(longestCommonPrefix(["flower","flow","flight"])) // fl
print(longestCommonPrefix(["dog","racecar","car"])) // empty
print(longestCommonPrefix(["geeksforgeeks", "geeks", "geek", "geezer"])) // gee
print(longestCommonPrefix(["apple", "ape", "april"])) // ap

Primary idea: Use the first string as the result at first, trim it while iterating the array Time Complexity: O(nm), Space Complexity: O(m), m stands for the length of longest prefix

func longestCommonPrefix(_ strs: [String]) -> String {
    // Get the first string of the array
    guard let firstStr = strs.first else {
        return ""
    }

    var res = ""

    // Iterate through the first string
    for (i, char) in firstStr.enumerated() {
        // Iterate through the remaining strings in the array
        // dropFirst(_ k: Int = 1) returns a Substring struct
        for str in strs.dropFirst() {
            // If there is a string with length equal the current index i, return the result
            if i == str.count {
                return res
            }


            // Get the current char of the current str at index i
            // Another easy way: Array(str)[i], time complexity is linear though
            let currentStrChar = str[str.index(str.startIndex, offsetBy: i)]

            // Compare the current char with the char from the first string
            if char != currentStrChar {
                return res
            }
        }

        res.append(char)
    }

    return res
}

print(longestCommonPrefix(["flower","flow","flight"])) // fl
print(longestCommonPrefix(["dog","racecar","car"])) // empty
print(longestCommonPrefix(["geeksforgeeks", "geeks", "geek", "geezer"])) // gee
print(longestCommonPrefix(["apple", "ape", "april"])) // ap