Ransom Note - tanakakenji/Rinko GitHub Wiki

はい、承知いたしました。以下に問題の回答と解説を示します。

問題:

2つの文字列 ransomNote と magazine が与えられたとき、magazine の文字を使って ransomNote を構築できる場合は true を、そうでない場合は false を返してください。

magazine の各文字は ransomNote で一度しか使用できません。

例:

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false
Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

制約:

1 <= ransomNote.length, magazine.length <= 10^5
ransomNote と magazine は小文字の英字で構成されています。

回答と解説:

この問題では、magazine 文字列に含まれる文字を使って ransomNote 文字列を構築できるかどうかを判定する必要があります。重要なのは、magazine の各文字は一度しか使用できないという制約です。

この問題を解決する効率的なアプローチは、各文字の出現回数をカウントすることです。

アプローチ 1: ハッシュマップ (辞書) を使用する

1. magazine の文字頻度をカウントする:

   • magazine 文字列を反復処理し、各文字の出現回数をハッシュマップ (または辞書) に格納します。キーは文字、値はその出現回数です。

2. ransomNote の文字をチェックする:

   • ransomNote 文字列を反復処理します。
   • ransomNote の各文字について、magazine の頻度マップにその文字が存在し、かつ出現回数が 0 より大きいかを確認します。
     • 文字が存在し、出現回数が正の場合、その文字を ransomNote で使用するため、頻度マップからその文字の出現回数を 1 減らします。
     • 文字が存在しないか、出現回数が 0 の場合、ransomNote を構築できないため、false を返します。

3. 成功:

   • ransomNote のすべての文字を問題なく処理できた場合、ransomNote は magazine から構築可能であるため、true を返します。

Python での実装例:

from collections import Counter

def canConstruct(ransomNote: str, magazine: str) -> bool:
    magazine_counts = Counter(magazine)
    for char in ransomNote:
        if magazine_counts[char] > 0:
            magazine_counts[char] -= 1
        else:
            return False
    return True

# 例
print(canConstruct("a", "b"))      # Output: False
print(canConstruct("aa", "ab"))     # Output: False
print(canConstruct("aa", "aab"))    # Output: True

解説:

• Counter(magazine) は、magazine 文字列内の各文字の出現回数をカウントし、辞書のようなオブジェクトを作成します。
• ransomNote の各文字について、magazine_counts にその文字が存在し、かつ出現回数が 0 より大きいかを確認しています。
• 条件を満たす場合、magazine_counts[char] -= 1 でその文字の使用回数を減らします。
• もし magazine_counts[char] が 0 以下の場合、その文字は magazine に不足しているか、すでに使い果たされているため、False を返します。
• ループが完了すれば、ransomNote は magazine から構築可能であるため、True を返します。

アプローチ 2: 配列を使用する (小文字の英字限定)

ransomNote と magazine が小文字の英字のみで構成されているという制約を利用して、配列を使って文字頻度を管理することもできます。

1. magazine の文字頻度をカウントする:

   • 長さ 26 の配列 (またはリスト) を用意し、各インデックスをアルファベットの各文字に対応させます (例: インデックス 0 は 'a'、インデックス 1 は 'b' など)。
   • magazine 文字列を反復処理し、各文字に対応する配列のインデックスの値をインクリメントします。

2. ransomNote の文字をチェックする:

   • ransomNote 文字列を反復処理します。
   • ransomNote の各文字について、対応する配列のインデックスの値が 0 より大きいかを確認します。
     • 値が正の場合、その文字を ransomNote で使用するため、配列の値を 1 デクリメントします。
     • 値が 0 の場合、ransomNote を構築できないため、false を返します。

3. 成功:

   • ransomNote のすべての文字を問題なく処理できた場合、ransomNote は magazine から構築可能であるため、true を返します。

Python での実装例 (配列を使用):

def canConstruct_array(ransomNote: str, magazine: str) -> bool:
    alphabet = [0] * 26
    for char in magazine:
        alphabet[ord(char) - ord('a')] += 1

    for char in ransomNote:
        index = ord(char) - ord('a')
        if alphabet[index] > 0:
            alphabet[index] -= 1
        else:
            return False
    return True

# 例
print(canConstruct_array("a", "b"))      # Output: False
print(canConstruct_array("aa", "ab"))     # Output: False
print(canConstruct_array("aa", "aab"))    # Output: True

時間計算量:

• どちらのアプローチも、magazine と ransomNote の文字列をそれぞれ一度反復処理するため、時間計算量は O(m + n) です。ここで、m は magazine の長さ、n は ransomNote の長さです。

空間計算量:

• ハッシュマップを使用するアプローチでは、最悪の場合、magazine に含まれるすべてのユニークな文字を格納するため、空間計算量は O(k) です。ここで、k は magazine 内のユニークな文字の数です。
• 配列を使用するアプローチでは、常に固定サイズの配列 (長さ 26) を使用するため、空間計算量は O(1) です。

結論:

どちらのアプローチも効率的ですが、配列を使用するアプローチは、問題の制約 (小文字の英字のみ) を利用することで、わずかに空間効率が良くなります。ハッシュマップを使用するアプローチは、より一般的な文字セットに対応できます。