383.ransom-note.md

問題

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

回答

初回の回答: magazine に ransom_note に含まれる文字が入っているかを contains()で確認する

これは普通に Accept されなかった。

• ransom_note: aa, magazine: aab -> true
• ransom_note: aa, magazine: aba -> false

前者は true と判定されるべきもの。contains()は string slice 一塊で評価されるので、問題の条件にはそぐわない。文字の順序関係なく、ransom_note に含まれる文字を magazine に含まれる文字で表現できるかを判定する必要がある。

impl Solution {
    pub fn can_construct(ransom_note: String, magazine: String) -> bool {
        magazine.contains(&ransom_note)
    }
}

---

二回目の回答: chars()にばらし、cmp()で iterator として比較する

これは一見良さそうに見えるけど、ransom_note に含まれる文字が一つも存在しない場合も true が帰ってしまうので通らなかった。

impl Solution {
    pub fn can_construct(ransom_note: String, magazine: String) -> bool {
        ransom_note.chars().cmp(magazine.chars()).is_le()
    }
}

---

三回目の回答: chars()にばらし、find()で発見した char を magazine から一つずつ削除していく

この方法を使えば、ransom_note の各文字が すべて magazine にヒットするかを判定できる。remove()は replace()と違って in place で magazine の値を書き換えるので、新たに String を生成する必要がない。

Runtime: 4 ms, faster than 63.28% of Rust online submissions for Ransom Note. Memory Usage: 2.1 MB, less than 94.12% of Rust online submissions for Ransom Note.

impl Solution {
    pub fn can_construct(ransom_note: String, magazine: String) -> bool {
        let mut magazine = magazine;
        ransom_note.chars().all(|char| {
            if let Some(n) = magazine.find(char) {
                magazine.remove(n);
                return true;
            }
            false
        })
    }
}

---

四回目の回答: HashMap を使ってアルファベットの出現回数を見る

ransom_note の各アルファベットの出現回数を HashMap に保存しておく。そして、magazine の各アルファベットの出現回数をそれぞれのバリューから引いていき、バリューの合計値が 0 になっていれば OK。

Runtime: 11 ms, faster than 27.63% of Rust online submissions for Ransom Note. Memory Usage: 2.2 MB, less than 68.09% of Rust online submissions for Ransom Note.

という結果になり、二回目の回答より遅かった。

impl Solution {
    pub fn can_construct(ransom_note: String, magazine: String) -> bool {
        let mut alphabets: HashMap<char, i32> = HashMap::new();
        ransom_note.chars().for_each(|c| {
            let value = alphabets.entry(c).or_insert(0);
            *value += 1;
        });
        println!("{:?}", alphabets);
        magazine.chars().for_each(|c| {
            if let Some(v) = alphabets.get_mut(&c) {
                if *v > 0 {
                    *v -= 1
                };
            }
        });
        println!("{:?}", alphabets);
        alphabets.values().sum::<i32>() <= 0
    }
}