Задача: 748. Shortest Completing Word
Сложность: easy

Вам дан целочисленный массив nums, в котором наибольшее целое число уникально. Определите, является ли наибольший элемент массива по крайней мере в два раза больше всех остальных чисел в массиве. Если да, то верните индекс самого большого элемента, в противном случае верните -1.

Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"

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

1⃣Извлечь все буквы из licensePlate, игнорируя цифры и пробелы, и создать словарь для подсчета частоты каждой буквы.

2⃣Пройти по массиву words, проверяя каждое слово на соответствие требованиям.

3⃣Найти самое короткое завершающее слово среди подходящих.

😎 Решение:

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        unordered_map<char, int> licenseCount = getCharCount(licensePlate);
        
        string result;
        for (const string& word : words) {
            if (isCompletingWord(word, licenseCount)) {
                if (result.empty() || word.length() < result.length()) {
                    result = word;
                }
            }
        }
        return result;
    }
    
private:
    unordered_map<char, int> getCharCount(const string& s) {
        unordered_map<char, int> count;
        for (char c : s) {
            if (isalpha(c)) {
                count[tolower(c)]++;
            }
        }
        return count;
    }
    
    bool isCompletingWord(const string& word, const unordered_map<char, int>& licenseCount) {
        unordered_map<char, int> wordCount;
        for (char c : word) {
            wordCount[c]++;
        }
        for (const auto& entry : licenseCount) {
            if (wordCount[entry.first] < entry.second) {
                return false;
            }
        }
        return true;
    }
};

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