LeetCode刷题【748】最短补全词

输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
输出："steps"
解释：最短补全词应该包括 "s"、"p"、"s"（忽略大小写） 以及 "t"。
"step" 包含 "t"、"p"，但只包含一个 "s"，所以它不符合条件。
"steps" 包含 "t"、"p" 和两个 "s"。
"stripe" 缺一个 "s"。
"stepple" 缺一个 "s"。
因此，"steps" 是唯一一个包含所有字母的单词，也是本例的答案。

输入：licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
输出："pest"
解释：licensePlate 只包含字母 "s" 。所有的单词都包含字母 "s" ，其中 "pest"、"stew"、和 "show" 三者最短。答案是 "pest" ，因为它是三个单词中在 words 里最靠前的那个。

哈希表，字符统计，简单，特纯粹的哈希表统计

1. 统计licensePlate中字符出现次数
2. 遍历words[] 分别统计每个word的字符出现次数
3. 对比两者统计结果，需要满足
   • 在licensePlate中出现的字符，在word中出现的次数要大于等于在licensePlate中出现的次数
   • 判断需要返回的结果ans 和当前word的长度，取较小的一个，相等的情况不变，即长度相等取现出现的

就…纯粹的哈希表统计

代码

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] arr = charCnt(licensePlate);
        String ans = null;
        for (String word : words) {
            int[] wArr = charCnt(word);
            boolean flag = true;
            for (int i = 0; flag && i < arr.length; i++) {
                if (arr[i]>0 && wArr[i] <arr[i]){
                    flag = false;
                }
            }
            ans = flag && ( ans == null || word.length() < ans.length()) ? word : ans;
        }
        return ans;
    }

    private int[] charCnt(String str){
        int[] arr = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c >= 'a' && c <= 'z'){
                arr[str.charAt(i)-'a']++;
            }
            if (c >= 'A' && c <= 'Z'){
                arr[str.charAt(i)-'A']++;
            }
        }
        return arr;
    }
}