X

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-解题思路分析/
Categories: leetcode
kwantong: