RansomNote [source code]

public class RansomNote {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] noteLetters = ransomNote.toCharArray();
        char[] magLetters = magazine.toCharArray();
        int[] counts = new int[26];
        for (char c : magLetters) counts[c - 'a']++;
        for (char c : noteLetters) {
            if (counts[c - 'a'] < 1) return false;
            counts[c - 'a']--;
        }
        return true;
    }
}

这个问题最开始的思路是两个reverse dictionary, 分别记录counter, 然后两者之间进行比较, 只要 magzine 里面的 counter 大于 note 里面的就行了;

但是这个比较其实可以整合在查询里面;
同是 dictionary 这里也可以用 array 而非 Map 来做, 因为我们单纯就是要一个 counter 而已, 同是 key 的 domain 是有限的;

除开这几个小技巧, 这个问题总体来说是很简单的, 应该是属于可以秒杀的题目, 标准的 CRUD 类问题(历史信息类问题);

速度是17ms, 80%;

Problem Description

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
Difficulty:Easy
Category:Algorithms
Acceptance:46.91%
Contributor: LeetCode
Companines
Apple
Related Topics
string