题目描述

为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。

给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。

如果可以构成，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ransom-note
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

• 今天的算法每日一题是字符串处理题目，我们主要用 ASCII 码知识，通过数组存储ransomNote字符出现的次数。然后循环便利 magazine，找到在 ransomNote 中出现的字符，减去出现的次数。最后判断ransomNote 的字符统计次数。如果某个字符大于0，则返回 false。 实现代码如下：

通过代码

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] ransomNoteArr = new int[26];
        for (char ch : ransomNote.toCharArray()) {
            ransomNoteArr[ch - 'a']++;
        }

        for (char ch : magazine.toCharArray()) {
            ransomNoteArr[ch - 'a']--;
        }

        boolean ans = true;
        for (int i = 0; i < 26; i++) {
            if (ransomNoteArr[i] > 0) {
                ans = false;
                break;
            }
        }

        return ans;
    }
}

总结

• 上述算法的时间复杂度是O(n),空间复杂度是O(n)

• 坚持算法每日一题，加油！