748.最短完備語

ID：748 TITLE：最短完備語TAG：Java、Python
方法：比較カウント
アルゴリズム:

私たちはwordとlicenseplateの中のアルファベットの数を計算して、小文字に変換して、アルファベットではない文字を無視します。単語の各文字のカウントがlicenseplateの中の文字数より大きい場合、licensePlateの完全な単語です。

私たちは最短の完全語と最初に出る単語を選ぶ必要があります。

class Solution(object):
    def shortestCompletingWord(self, licensePlate, words):
        def count(itera):
            ans = [0] * 26
            for letter in itera:
                ans[ord(letter) - ord('a')] += 1
            return ans

        def dominates(c1, c2):
            return all(x1 >= x2 for x1, x2 in zip(c1, c2))

        ans = None
        target = count(c.lower() for c in licensePlate if c.isalpha())
        for word in words:
            if ((len(word) < len(ans) or ans is None) and
                    dominates(count(word.lower()), target)):
                ans = word

        return ans

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] target = count(licensePlate);
        String ans = "";
        for (String word: words)
            if ((word.length() < ans.length() || ans.length() == 0) &&
                    dominates(count(word.toLowerCase()), target))
                ans = word;
        return ans;
    }

    public boolean dominates(int[] count1, int[] count2) {
        for (int i = 0; i < 26; ++i)
            if (count1[i] < count2[i])
                return false;
        return true;
    }

    public int[] count(String word) {
        int[] ans = new int[26];
        for (char letter: word.toCharArray()){
            int index = Character.toLowerCase(letter) - 'a';
            if (0 <= index && index < 26)
                ans[index]++;
        }
        return ans;
    }
}

複雑度の分析

時間複雑度：O（N）O（N）O（N）。N N Nとは、wordsの要素個数を指し、licensePlateとwords[i]のアルファベットカウントを比較するとO（1）O（1）O（1）の時間が必要となる

を指す。

空間複雑度：O（1）O（1）O（1）定数の空間を使用します。