LeetCodeの復習(2)

Word Subsets

どんな問題？

• words1: string[]中の文字列aが、words2: string[]内の全文字列bを「サブセット（bの文字をaで余さず含む）」として含むか判定し、すべて満たすaを返す問題。

• b = "wrr" は a = "warrior" のサブセット

  • "warrior" の中に 'w' が1個、'r' が2個 あるので、"wrr" も作れる

• b = "wrr" は a = "world" のサブセットではない

  • "world" の中には 'r' は1個しかないので、"wrr" を作れない

• 例

  • Input:

    • words1 = ["acaac","cccbb","aacbb","caacc","bcbbb"]

    • words2 = ["c","cc", "cb", "bb"]

  • Output: ["cccbb"]

考え方

1. words2の全文字列の文字数を数える

   1. "c" → "c"が1つ

   2. "cc" → "c"が2つ

   3. "cb":"c"が1つと"b"が1つ

   4. "bb": "b"が2つ

2. word1の含まれるべき文字と文字数を計算する

   1. word1の各文字列には"c"が2つと, "b"が2つ必要

3. word1の各文字列を捜査して、2で含まれるべき文字と文字数が満たされるものを抽出して返却する

(私の回答)

function wordSubsets(words1: string[], words2: string[]): string[] {
    const answer = []
    const charCountMap = new Map<string, number>()
    for (const word2 of words2) {
        const map = new Map<string, number>()
        word2.split("").forEach(char => {
            map.set(char, (map.get(char) ?? 0) + 1)
        })
        map.forEach((count, char) => {
            charCountMap.set(char, Math.max(charCountMap.get(char) ?? 0, count))
        })
    }

    for (const word1 of words1) {
        const map = new Map<string, number>()
        word1.split("").forEach(char => {
            map.set(char, (map.get(char) ?? 0) + 1)
        })
        let isSubset = true;
        for (const [char, count] of charCountMap) {
            isSubset = (map.get(char) ?? 0) >= count
            if (!isSubset) {
                break;
            }
        }
        if (isSubset) {
            answer.push(word1)
        }
    }
    return answer;
};

公式の回答

function wordSubsets(words1: string[], words2: string[]): string[] {
    const answer = []
    const maxCounts = new Array(26).fill(0);
    for (const word2 of words2) {
        const counts = new Array(26).fill(0);
        for (const char of word2) {
            counts[char.charCodeAt(0) - 'a'.charCodeAt(0)]++
        }
        for (let i = 0; i < 26; i++) {
            maxCounts[i] = Math.max(maxCounts[i], counts[i])
        }
    }

    for (const word1 of words1) {
        const counts = new Array(26).fill(0);
        for (const char of word1) {
            counts[char.charCodeAt(0) - 'a'.charCodeAt(0)]++
        }
        let isUniversal = true;
        for (let i = 0; i < 26; i++) {
            if (counts[i] < maxCounts[i]) {
                isUniversal = false;
                break;
            }
        }
        if (isUniversal) {
            answer.push(word1)
        }
    }
    return answer;
};

私はword2の文字列を集計したり、word1で含まれているかを確認するのにMapを使用した

• words2に含まれるのは{"b": 2, "c": 2}

• word1にはそれぞれ{"a": 2, c: 2}, {"b": 2, "c": 3}…

公式の回答は26個の要素を持った配列を用意し、そこでカウントしていく方法

• words2 は [0, 2 , 2, 0 …0]

  • index = 0の値は'a'の個数

  • index = 1の値は'b'の個数 (2個)

  • index = 2の値は'c'の個数 (2個)

• words1は [2, 0, 2, …], [0, 2, 3, …] 

感想

アルファベットが26文字であることを利用して、扱いやすい26個の要素の配列に格納する方法が印象的だった