LEETCODE 383. Ransom Note 解题思路分析

题目大意：

赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设两个字符串均只含有小写字母。

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=383

解题思路分析：

这道题目实际上是在求ransom中的字符以及其个数，是否在magazines中出现过。因此解题时我们可以先统计出magazines中每种字符的个数，我们使用一个长度为26位的int型数组来做统计，下标0-25分别代表字母a-z。然后再遍历一遍ransom中每个字符，每循环至一个字符，我们减少magazines中对应该字符的个数，如果该字符个数变为负数，说明magazines中没有包含足够多的该字符，返回false。循环结束后如果所有字符个数仍都大于等于0，返回true。

实现代码：

public boolean canConstruct(String ransomNote, String magazine) {
    int[] count=new int[26];
    // 统计magazine中每种字符个数
    for(int i=0;i<magazine.length();i++){
        count[magazine.charAt(i)-'a']++;
    }
    // 循环ransomNote每个字符
    for(int i=0;i<ransomNote.length();i++){
        // 当前字符个数减一
        count[ransomNote.charAt(i)-'a']--;
        // 如果当前字符个数小于0，返回false
        if(count[ransomNote.charAt(i)-'a']<0) return false;
    }
    return true;
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 70.22% of Java online submissions for Ransom Note.

Memory Usage: 39 MB, less than 84.62% of Java online submissions for Ransom Note.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-383-ransom-note-解题思路分析/