Задача: 916. Word Subsets
Сложность: medium

Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.

Пример:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

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

1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2.

2⃣Проверить каждое слово из words1, если оно содержит не менее максимального количества каждой буквы, которая встречается в словах из words2.

3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<string> WordSubsets(string[] words1, string[] words2) {
        int[] maxCount = new int[26];
        foreach (string word in words2) {
            int[] count = GetCount(word);
            for (int i = 0; i < 26; i++) {
                maxCount[i] = Math.Max(maxCount[i], count[i]);
            }
        }

        List<string> result = new List<string>();
        foreach (string word in words1) {
            int[] count = GetCount(word);
            if (IsUniversal(count, maxCount)) {
                result.Add(word);
            }
        }

        return result;
    }

    private int[] GetCount(string word) {
        int[] count = new int[26];
        foreach (char c in word) {
            count[c - 'a']++;
        }
        return count;
    }

    private bool IsUniversal(int[] count, int[] maxCount) {
        for (int i = 0; i < 26; i++) {
            if (count[i] < maxCount[i]) {
                return false;
            }
        }
        return true;
    }
}

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