[LeetCode刷題筆記] 916 – Word Subsets

題目描述：

We are given two arrays A and B of words. Each word is a string of lowercase letters.

Now, say that word b is a subset of word a if every letter in b occurs in a, including multiplicity. For example, "wrr" is a subset of "warrior", but is not a subset of "world".

Now say a word a from A is universal if for every b in B, b is a subset of a.

Return a list of all universal words in A. You can return the words in any order.

Example 1:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["l","e"]
Output: ["apple","google","leetcode"]

Example 3:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["e","oo"]
Output: ["facebook","google"]

Example 4:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["lo","eo"]
Output: ["google","leetcode"]

Example 5:

Input: A = ["amazon","apple","facebook","google","leetcode"], B = ["ec","oc","ceo"]
Output: ["facebook","leetcode"]

Note:

1. 1 <= A.length, B.length <= 10000
2. 1 <= A[i].length, B[i].length <= 10
3. A[i] and B[i] consist only of lowercase letters.
4. All words in A[i] are unique: there isn’t i != j with A[i] == A[j].

一刷題解（Brute Force）：

這題給了我們兩個字符串數組，A字符串數組裡的都是一些完整的字符串，而B字符串數組裡則都是一些字符碎片，題目要我們在A字符串數組中找到一些字符串，這些字符串中各類字母，包含且大於B字符串中的各類字母出現的最大數量。

因此，我們可以先統計B字符串數組中，各類字母出現的最大次數，並將其放到一個容量為26的數組裡（發揮字母出現次數字典的功能）。完成B的統計後，我們再逐一統計每個A字符串裡，出現的字母是否包括了B字符串的字母，出現次數是否大於B字符串字母的出現次數，如果兩者答案均為肯定，那就代表這個A字符串是我們的其中一個答案。

public class Solution {
    public IList<string> WordSubsets(string[] A, string[] B)
    {
        List<string> result = new List<string>();

        //字母出現統計數組
        int[] charAppearCnt = new int[26];


        //統計B中的字符裡的每類字母出現的最大數量
        for (int i = 0; i < B.Length; i++)
        {
            int[] cntArr = CharCount(B[i]);

            for (int j = 0; j < cntArr.Length; j++)
            {
                if (cntArr[j] == 0) { continue; }
                if (charAppearCnt[j] < cntArr[j])
                {
                    charAppearCnt[j] = cntArr[j];
                }
            }
        }


        //檢查A中的字符的各類字母是包含且大於字典裡的記錄
        for (int i = 0; i < A.Length; i++)
        {
            bool isUniversal = true;
            int[] cntArr = CharCount(A[i]);

            for (int j = 0; j < cntArr.Length; j++)
            {
                //只需要檢查B字符串裡存在的字母，其他沒出現過的字母跳過檢查
                if (charAppearCnt[j] == 0) { continue; }
                //如果A中字母出現次數少於B字符字母的出現次數，該字符B就不是字符A的Subset
                if (cntArr[j] < charAppearCnt[j])
                {
                    isUniversal = false;
                    break;
                }
            }

            if (isUniversal)
            {
                result.Add(A[i]);
            }
        }

        return result;
    } 
    
    int[] CharCount(string str)
    {
        int[] cntArr = new int[26];
        foreach (char c in str.ToCharArray())
        {
            cntArr[c - 'a'] += 1;
        }
        return cntArr;
    }
}