Задача: 318. Maximum Product of Word Lengths
Сложность: medium

Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0.

Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

👨‍💻 Алгоритм:

1⃣Предварительная обработка масок и длин
Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens.

2⃣Сравнение слов и проверка общих букв
Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd.

3⃣Возврат результата
Верните максимальное значение произведения maxProd.

😎 Решение:

class Solution {
    func maxProduct(_ words: [String]) -> Int {
        let n = words.count
        var masks = [Int](repeating: 0, count: n)
        var lens = [Int](repeating: 0, count: n)
        
        for i in 0..<n {
            var bitmask = 0
            for ch in words[i] {
                bitmask |= 1 << (ch.asciiValue! - Character("a").asciiValue!)
            }
            masks[i] = bitmask
            lens[i] = words[i].count
        }
        
        var maxVal = 0
        for i in 0..<n {
            for j in i+1..<n {
                if masks[i] & masks[j] == 0 {
                    maxVal = max(maxVal, lens[i] * lens[j])
                }
            }
        }
        return maxVal
    }
}

Ставь 👍 и забирай 📚 Базу знаний