Easy

题目描述

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= ransomNote.length, magazine.length <= 10^5
  • ransomNote 和 magazine 由小写英文字母组成

解题思路

这道题本质上是检查一个字符串的字符能否完全由另一个字符串的字符组成，每个字符只能使用一次。

解题思路：

最直观的解法是使用哈希表统计字符频次。我们可以先统计 magazine 中每个字符的出现次数，然后遍历 ransomNote，对于每个字符，检查它在 magazine 中是否还有剩余可用次数。如果某个字符不存在或已用完，返回 false；否则将该字符的可用次数减一。

优化思路：

由于题目明确说明只包含小写英文字母，我们可以用长度为26的数组代替哈希表，以字符ASCII值减去’a’作为索引，这样空间复杂度是常数级别的。

算法步骤：

  1. 创建长度为26的计数数组，统计 magazine 中每个字符的频次
  2. 遍历 ransomNote 中的每个字符
  3. 如果当前字符在数组中的计数为0，说明无法构成，返回 false
  4. 否则将该字符的计数减1
  5. 遍历完成后返回 true

代码实现

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> count(26, 0);
        
        // 统计magazine中每个字符的频次
        for (char c : magazine) {
            count[c - 'a']++;
        }
        
        // 检查ransomNote中的每个字符
        for (char c : ransomNote) {
            if (count[c - 'a'] == 0) {
                return false;
            }
            count[c - 'a']--;
        }
        
        return true;
    }
};

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        count = [0] * 26
        
        # 统计magazine中每个字符的频次
        for c in magazine:
            count[ord(c) - ord('a')] += 1
        
        # 检查ransomNote中的每个字符
        for c in ransomNote:
            if count[ord(c) - ord('a')] == 0:
                return False
            count[ord(c) - ord('a')] -= 1
        
        return True

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        int[] count = new int[26];
        
        // 统计magazine中每个字符的频次
        foreach (char c in magazine) {
            count[c - 'a']++;
        }
        
        // 检查ransomNote中的每个字符
        foreach (char c in ransomNote) {
            if (count[c - 'a'] == 0) {
                return false;
            }
            count[c - 'a']--;
        }
        
        return true;
    }
}

var canConstruct = function(ransomNote, magazine) {
    const count = new Array(26).fill(0);
    
    // 统计magazine中每个字符的频次
    for (const c of magazine) {
        count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    // 检查ransomNote中的每个字符
    for (const c of ransomNote) {
        const index = c.charCodeAt(0) - 'a'.charCodeAt(0);
        if (count[index]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m + n)m为magazine长度，n为ransomNote长度，需要遍历两个字符串各一次
空间复杂度O(1)使用固定大小的数组（26个元素）存储字符计数

相关题目