0748. Shortest Completing Word #

题目 #

给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出 words 中的 最短补全词 。
补全词 是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的 数字和空格 。不区分大小写。如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。
例如：licensePlate`` = "aBc 12c"，那么它的补全词应当包含字母 'a'、'b' （忽略大写）和两个 'c' 。可能的 补全词 有 "abccdef"、"caaacab" 以及 "cbca" 。
请返回 words 中的 最短补全词 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中 第一个 出现的那个。

思路 #

哈希 #

代码 #

哈希 #

class Solution {
    public int[] statistics;

    public void getStatistics(String word, int[] cnt) {
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            if (Character.isLetter(ch)) {
                cnt[ch <= 'Z' ? ch - 'A' : ch - 'a']++;
            }
        }
    }

    public boolean valid(String word) {
        int[] cnt = new int[26];
        this.getStatistics(word, cnt);

        for (int i = 0; i < 26; i++) {
            if (statistics[i] > cnt[i]) return false;
        }
        return true;
    }

    public String shortestCompletingWord(String licensePlate, String[] words) {
        this.statistics = new int[26];
        this.getStatistics(licensePlate, this.statistics);

        int len = Integer.MAX_VALUE;
        String ans = "";

        for (String word: words) {
            if (this.valid(word) && word.length() < len) {
                len = word.length();
                ans = word;
            }
        }

        return ans;
    }
}

致谢 #

宫水三叶