题解 | #字符串构造判定#

题目链接

题目描述

给定两个仅由小写英文字母构成的字符串 ransomNote 和 magazine。

请判断是否可以从 magazine 中选取若干字符（每个字符最多使用一次），拼接成与 ransomNote 完全相同的字符串。

这是一个 核心代码模式 (Core Code Mode) 的题目，你只需要实现 canConstruct 函数。

示例 1: 输入:

"wc", "nowcoder"

输出:

true

解题思路

这道题的本质是检查 "magazine 字符串中的字符数量，是否足够满足 ransomNote 字符串中每个字符的需求"。

我们可以使用 字符计数（哈希表） 的方法来高效解决。由于题目限定字符都是小写英文字母，我们可以用一个大小为 26 的数组来充当哈希表，这比通用的 HashMap 或 unordered_map 效率更高。

算法步骤:

初步剪枝: 如果 ransomNote 的长度大于 magazine 的长度，那么 magazine 肯定无法凑出 ransomNote，可以直接返回 false。这是一个有效的优化。
建立字符库: 创建一个大小为 26 的整型数组 counts。遍历 magazine 字符串，统计其中每个字符出现的次数。例如，遇到字符 'a'，就将 counts[0] 加一；遇到 'b'，就将 counts[1] 加一，以此类推（counts[ch - 'a']++）。
消耗字符: 遍历 ransomNote 字符串。对于遇到的每一个字符 ch，我们从字符库中"取走"一个，即将 counts 数组中对应的计数减一（counts[ch - 'a']--）。
检查库存: 在每次消耗字符后，立刻检查该字符的库存是否足够。如果 counts 中对应的值变为负数，说明 magazine 中没有足够的该种字符来构造 ransomNote，应立即返回 false。
成功构造: 如果整个 ransomNote 遍历完成，都没有出现库存不足的情况，说明 magazine 中的字符足够，可以成功构造。返回 true。

代码

cpp
java
python

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param ransomNote string字符串 
     * @param magazine string字符串 
     * @return bool布尔型
     */
    bool canConstruct(string ransomNote, string magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        
        vector<int> counts(26, 0);
        for (char ch : magazine) {
            counts[ch - 'a']++;
        }
        
        for (char ch : ransomNote) {
            counts[ch - 'a']--;
            if (counts[ch - 'a'] < 0) {
                return false;
            }
        }
        
        return true;
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param ransomNote string字符串 
     * @param magazine string字符串 
     * @return bool布尔型
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        
        int[] counts = new int[26];
        for (char ch : magazine.toCharArray()) {
            counts[ch - 'a']++;
        }
        
        for (char ch : ransomNote.toCharArray()) {
            counts[ch - 'a']--;
            if (counts[ch - 'a'] < 0) {
                return false;
            }
        }
        
        return true;
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param ransomNote string字符串 
# @param magazine string字符串 
# @return bool布尔型
#
from collections import Counter
class Solution:
    def canConstruct(self , ransomNote: str, magazine: str) -> bool:
        # 如果赎金信更长，直接返回 False
        if len(ransomNote) > len(magazine):
            return False
        
        # 使用 Counter 进行字符计数，非常高效和 Pythonic
        # a - b 会得到一个计数器，其中包含 a 有但 b 没有或 b 不足的元素
        # 如果结果为空或者所有值的计数都小于等于0，则说明 b 足以构成 a
        return not (Counter(ransomNote) - Counter(magazine))

算法及复杂度

算法: 字符计数 (Frequency Array / Hash Map)
时间复杂度: $\mathcal{O}(M+N)$ ，其中 $M$ 是 magazine 的长度， $N$ 是 ransomNote 的长度。我们需要分别遍历两个字符串一次。
空间复杂度: $\mathcal{O}(|\Sigma|)$ 或 $\mathcal{O}(1)$ ，其中 $|\Sigma|$ 是字符集的大小（本题中为26）。由于字符集大小是固定的，所以空间复杂度为常数。