LeetCode / Ransom Note

リハビリその2。

https://leetcode.com/problems/ransom-note/

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

Ransom Noteは身代金を要求する手紙のことのようですが、なぜこの問題がRansome Note?と思ったら、昔のそういった手紙は新聞や雑誌の切り抜きで文章を作っていたため、ということですね。
変数名がmagazineというところで気がつきました。

難易度はとても低いです。問題タイトルと内容の対応を読み解くところがこの問題のハイライトな気がします。

解答・解説

解法1

文字列のままループを回し、変数magazineからransomNoteを構成する文字を剥ぎ取っていきます。まさに脅迫状作成プロセスを逆回ししている感じです。

replaceの第三引数は、第一引数の値が存在した場合いくつ置換するかを表します。あまり普段の言語処理で使うことがない引数なので、ググってしまいました。

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        for i in ransomNote:
            if i in magazine:
                magazine = magazine.replace(i, '', 1)
            else:
                return False
        return True

解法2

リストに変換してもほとんど同様に解けますが、リスト化の分計算コストが高い。

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        l_ran = [s for s in ransomNote]
        l_mag = [s for s in magazine]
        for i in l_ran:
            if i in l_mag:
                l_mag.remove(i)
            else:
                return False
        return True