14. Longest Common Prefix

Third edition of my LeetCode journey :)

The problem

In this problem, we need to find the longest common prefix among an array of strings.

For example, for this input:

["flower", "flow", "flight"]

The longest common prefix is:

"fl"

Because all words start with "fl".

Another example:

["dog", "racecar", "car"]

In this case, there is no common prefix, so the answer should be:

""

The idea

The idea is to compare the characters of each word, position by position.

First, I convert each string into an array of characters:

let strs = strsRaw.map { Array($0) }

This makes it easier to access each character by index.

Then, I get the size of the shortest string:

let minimumSize = strs.map { $0.count }.min() ?? 0

This is important because the common prefix can never be longer than the shortest word.

For example:

["flower", "flow", "flight"]

The shortest word is "flow", with size 4.

So we do not need to check positions after that.

After that, I loop through each character position:

for i in 0..<minimumSize {

For each position, I get the character from the first string:

let currentChar = strs[0][i]

Then I compare this character with the same position in all the other strings:

for str in strs.dropFirst() {
    if str[i] != currentChar {
        return longestPrefix
    }
}

If one character is different, it means the common prefix ended, so we return what we already built.

If all characters are equal at that position, we add the character to the answer:

longestPrefix.append(currentChar)

Full code

class Solution {
    func longestCommonPrefix(_ strsRaw: [String]) -> String {
        let strs = strsRaw.map { Array($0) }
        let minimumSize = strs.map { $0.count }.min() ?? 0

        var longestPrefix = ""

        for i in 0..<minimumSize {
            let currentChar = strs[0][i]

            for str in strs.dropFirst() {
                if str[i] != currentChar {
                    return longestPrefix
                }
            }

            longestPrefix.append(currentChar)
        }

        return longestPrefix
    }
}

Time complexity

The time complexity is O(n * m).

Where:

n = number of strings
m = length of the shortest string

In the worst case, we need to compare every character of the shortest string with every other string.

The space complexity is O(total characters) in this version, because we convert each string into an array of characters.

Thanks for reading!