题解 | #字符串构造判定#
字符串构造判定
https://www.nowcoder.com/practice/8d6a87b1e5314c0387dad5728dcc05be
题目链接
题目描述
给定两个仅由小写英文字母构成的字符串 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。
代码
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)
- 时间复杂度:
，其中
是
magazine的长度，是
ransomNote的长度。我们需要分别遍历两个字符串一次。 - 空间复杂度:
或
，其中
是字符集的大小（本题中为26）。由于字符集大小是固定的，所以空间复杂度为常数。
