Ransom Note字符串题核心：用频率计数模型破解UVa 10580

1. 题面第一眼容易理解错的三件事UVa 10580 Ransom Note 是很多人在字符串入门阶段绕不开的一道题。题面讲的是勒索信的场景有人从杂志或报纸上剪下字母拼成一句威胁的话现在给你一封“信”和一份“杂志文本”让你判断这封信里的字母能不能全部由杂志里的字母拼出来。题目本身并不难但它有两个非常容易想偏的地方我第一次做的时候就在这两个地方各 WA 了一回。这篇文章就围绕这道题把题目本质、解题模型、代码细节和踩坑记录完整拆一遍。先说结论这道题跟“字符串匹配”没有关系。很多人看到 Ransom Note 就以为是判断信的文字是否出现在杂志里或者信里的每个单词是否都能在杂志里找到这全都偏了。信上的字母是单个剪下来又重新排列的全乱序也没关系杂志里也不需要出现完整单词。真正要比较的只有每个英文字母在两边出现的次数。1.1 不是找子串是数次数我举个最简单的例子信是abc杂志是cba。如果你在杂志里找单词abc找不到但这道题的答案必然是 Yes因为这封信所需要的一个a、一个b、一个c杂志里全都具备。反过来信是ab杂志里只有a那答案就是 No因为你少了一个b。再比如信是need杂志是a nice day。杂志里看似有n、e、e、d吗拆开看a n i c e d a y字母e只有一个信里需要两个e所以答案是 No。这种例子一旦想通题目的本质就出来了它是在比较字母频数。信里的每个字母需求量都要小于等于杂志里的供应量。所以第一件事就是把“能不能拼出来”翻译成“数量够不够”。思路不要停留在词、句、子串这种层面要往下沉到字母的颗粒度。1.2 只有大小写字母参与统计题目里的文本可能带空格、逗号、句号、数字、下划线甚至各种标点符号。这些东西要不要算答案是都不算。参与比较的只有英文字母 A-Z / a-z。这一点很容易被忽略是因为样例输入通常写得干干净净大家用肉眼一看就觉得“这两行差不多嘛”然后直接按全量字符处理。但你一旦遇到这样的用例信 Hello, world 123! 杂志hheelllloo wwoorrlld如果你把空格、逗号、数字也算进去统计一定乱掉如果只统计字母就会看到信所需的H e l l o w o r l d各字母都能在杂志里找到足够数量答案应该是 Yes。我在早期版本里图省事直接拿整个字符串长度来比较结果样例通过、提交就挂。原因就是我没有过滤非字母字符。后来我把统计逻辑改成“只有落在字母范围内的字符才进入计数”问题立刻消失。1.3 大小写不区分多组数据别漏读这道题默认大小写不区分A和a算同一个字母。所以实现时要先统一方向要么都转成大写要么都转成小写再做下标映射。有些人不做统一直接把大写字母算到 0-25 格子里又把小写字母算到另一组格子里那当然对不上。另外还有输入格式的问题。UVa 老题的输入描述通常很抽象不同题库复述出来的版本也有差异。比较常见的版本是多组测试数据每组两行第一行是信第二行是杂志一直读到 EOF 结束。因为两行都可能带空格所以必须用getline()而不是cin 。如果只考虑一组数据就提交代码只会处理第一组后面的输入全部作废这种毛病在入门题里非常典型。2. 把“拼字母”转化成频率计数模型一旦识别出题目的核心是“频数够不够”解法就非常清晰了。这不是什么高级算法只是一个最基本的计数思想用容器记录杂志提供了哪些字母、各有多少个然后检查信的需求能不能被满足。2.1 一个长度为 26 的数组足够字母总共只有 26 个所以一个int cnt[26]数组就能完整表达任意文本的字母构成。数组下标用字母本身映射出来a对应下标 0b对应下标 1依此类推。映射方法有两种写法。一种是用c - a要求c是小写另一种是用c - A要求c是大写。因为题目不区分大小写所以我在实现时会把A-Z和a-z分别做一次判断统一映射到同一个小写下标区间。这样不管是哪个字母最终落点都是 0 到 25。有人可能会问为什么不用字符串的字符集来做比如用int cnt[256]把所有 ASCII 字符都放进去然后只统计字母最后也只检查字母那部分下标。这个方案也能跑但浪费空间而且256这个量级会让人忽略“题目真正参与的元素只有 26 个”这一事实。用26会让代码的意图更明显也更容易在检查阶段遍历完整。2.2 “杂志先加、信再减”的顺序为什么更好常见的实现方案有两种。方案一是先统计杂志遍历杂志文本遇到字母就cnt[idx]。再遍历信遇到字母就判断cnt[idx]是否大于 0如果等于 0 直接返回 false否则执行cnt[idx]--。这种“供应先入库需求再出库”的顺序最贴近日常逻辑。方案二是先统计信再统计杂志最后对比每个下标need[i] have[i]。这个方案也能得到正确答案但代码更啰嗦而且无法提前终止必须把两边都统计完才能下结论。我推荐方案一。原因有两个第一它天然支持提前返回一旦发现某个字母缺货不用继续做无谓的遍历第二它不会出现负数计数。负数虽然也能说明“不够”但负数会让后续调试变得不直观比如数组里出现-5你还得想是哪个字母欠了 5 个。方案一永远是“不够就返回 false”逻辑链路非常干净。2.3 排序、find、map 三种替代方案的性价比有人会想我直接对信和杂志做排序然后逐位比较不行吗不行。因为文本里大量非字母字符会干扰排序结果而且把空格、数字混在字母里排序后逐位比较的规则会变得很复杂。排序本身是 O(n log n)对这道题来说完全可以过但它没有利用“只关心 26 种字母”这个关键信息属于杀鸡用牛刀。也有人会用find()函数每拿到信里的一个字符就在杂志里找找到就删掉一个。这个思路方向是对的但实现上非常容易出 bug。比如用std::string::find找到的永远是第一个匹配位置同一个字符出现多次时你删一个下一次再找还是会从开头开始找效率极差而且一旦信和杂志存在交叉顺序很容易把“同一位置反复匹配”当成成功。还有人会想到std::map或unordered_map。这个当然也能解但完全没有必要。26 种固定枚举用数组就是最优解map 的哈希操作和内存分配反而更慢。竞赛环境里养成“能用数组就不用容器”的习惯会少踩很多坑。复杂度方面设信的长度为 n杂志的长度为 m。统计阶段遍历一次 m检查阶段遍历一次 n总复杂度 O(nm)空间是固定的 26 个 int也就是 O(1)。对 UVa 的输入规模来说这是最优档。3. 完整代码与容易看漏的实现细节下面给出一份可直接提交的 C17 参考实现。代码不长但每一行都有它存在的理由。3.1 C17 参考实现#include bits/stdc.h using namespace std; int cnt[26]; bool canForm(const string note, const string magazine) { memset(cnt, 0, sizeof(cnt)); for (char c : magazine) { if (c a c z) cnt[c - a]; else if (c A c Z) cnt[c - A]; } for (char c : note) { int idx -1; if (c a c z) idx c - a; else if (c A c Z) idx c - A; else continue; if (cnt[idx] 0) return false; cnt[idx]--; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string note, magazine; while (getline(cin, note)) { if (!getline(cin, magazine)) break; cout (canForm(note, magazine) ? Yes : No) \n; } return 0; }我特意把统计函数拆出来而不是全塞在main里这样主循环结构更清楚也方便以后换成其他题目复用。memset(cnt, 0, sizeof(cnt))放在函数开头可以保证每组数据都有全新的计数环境。3.2 逐段拆解主循环与统计函数主循环用的是while (getline(cin, note))。如果连第一行都没读到说明已经 EOF直接退出如果第一行读到了但第二行缺失说明输入本身不完整break掉比强行输出一个答案更安全。ios::sync_with_stdio(false)和cin.tie(nullptr)这两句是竞赛标配作用是解除 C 输入输出流与 C 标准 IO 的同步让getline在大数据下更快。统计函数里我特意没有用isalpha而是自己写字符范围判断。不是因为isalpha不能用而是它有两个隐藏坑第一isalpha返回的是“非零值”而不一定是 1新手经常写成if (isalpha(c) 1)然后发现逻辑在部分环境下不稳定第二它受本地化影响可能把一些非 ASCII 字符也判成字母。直接用c a c z这种写法行为完全确定不需要记任何函数语义。大小写处理上我让大写字母和小写字母映射到同一个下标区间也就是c - A和c - a都指向 0-25。这样无论输入是大写还是小写统计结果都在同一套计数格里。3.3 带结束标记的改进版有些 UVa 题的输入格式不是读到 EOF而是要求遇到某一行固定的结束标记就停止。以我在不同题库里见到的情况Ransom Note 的某些镜像版会用单独一行END表示测试数据结束。如果要适配这种格式只需要修改主循环while (getline(cin, note)) { if (note END) break; if (!getline(cin, magazine)) break; cout (canForm(note, magazine) ? Yes : No) \n; }有一个细节需要注意判到END就要直接break不要继续读下一行杂志否则会把结束标记后面的数据误当成新一组样例。也不要把END当成一封信去输出那会多打一行结果。3.4 用 map 或 Python 的替代写法如果换到其他不要求性能的场合用unordered_map写会直观很多unordered_mapchar, int have; for (char c : magazine) if (isalpha(c)) have[tolower(c)]; for (char c : note) { if (!isalpha(c)) continue; char lower tolower(c); if (--have[lower] 0) return false; } return true;这种写法在概念上跟数组方案一模一样只是把 26 格固定数组换成了哈希表。好处是逻辑直观坏处是慢一点而且unordered_map的迭代顺序不确定对竞赛题来说没必要引入不确定性。Python 的写法更是几行就能搞定使用collections.Counterfrom collections import Counter note input() magazine input() need Counter(c.lower() for c in note if c.isalpha()) have Counter(c.lower() for c in magazine if c.isalpha()) print(Yes if all(need[k] have[k] for k in need) else No)这版代码简单归简单但如果输入是多组数据别忘记包一层循环而且每组之间清空 Counter。4. WA 排查链路与边界用例这道题我前前后后刷了三遍也见过不少人在讨论区问为什么 WA。下面把最常见的几种翻车现场按顺序还原出来每一条都是我或身边的人真实踩过的排查链路非常典型。4.1 第一版用 find 逐个匹配字母我最初的想法是既然杂志里有这个字母就行那我直接遍历信里的每个字符在杂志字符串里调用find()找到就把它删掉。逻辑听起来很通顺但实现时立刻暴露问题。find()每次返回的是第一个匹配位置。比如信是aa杂志是a第一次找a找到了把杂志里的a删掉第二次再找a就找不到了最终判定 No这是对的。问题出在杂志有多个相同字母、且位置交错时比如信是ab杂志是ba。第一次找a找到下标 1删掉后杂志变成b第二次找b找到下标 0也能继续。但信是aa杂志是a逻辑能够兜住信是aaa杂志是aa第一次删除后杂志变成a第二次删除后杂志为空第三次找不到也能兜住。真正的坑是我用find时没有把“找到后立即删除”和“本次查找应该从哪个位置开始”这两件事处理好会导致同一个字符被重复匹配。比如信是ab杂志是aab第一次找a找到下标 0删掉后杂志变成ab第二次找b找到下标 1这没问题。但如果我为了省事不是删除而是用一个标记数组记录“这个位置已经用过”遍历信的字符时每次从杂志开头找第一个未被标记的匹配字符那么信要是aa杂志是aa第一个a标记下标 0第二个a标记下标 1两个位置都正确。听起来没问题可只要杂志是ba信是aa第一次找a标记下标 1第二次找a再从开头扫描时发现下标 1 已被标记于是返回失败可实际上杂志里有两个a吗没有所以失败正确。但换成杂志aab信aaa第一次找a标记 0第二次找a标记 1第三次找不到可用的a失败正确。看似能算对。这套逻辑后来挂在一个更隐蔽的例子上信需要a杂志是bafind能成功信需要b杂志是ba也能成功但信需要ab杂志是ba就要求同时存在一个a和一个b。我用“每找一个字符就扫一遍整个杂志”的方式第一次找a标记了位置 1第二次找b从开头扫到位置 0也找到了好像也能过。真正让它崩溃的是信aba杂志ab——这本身该判 No但我那套标记逻辑找不到可用的a时返回 false结果也是 No。说明这种错误实现不一定每个用例都错但复杂度已经是明显的 O(n*m)在大数据下直接超时。后来我彻底抛弃了“逐个找字符”的思路改成先统计完整频数再比较。这一版才终于稳定。4.2 第二版cin 处理带空格的输入第一版算法错了之后我想换成频数统计但写代码时偷懒用了cin note。本地测试样例时两组数据都不带空格所以没问题。一换成带空格的数据cin 读到空格就停止信里空格后面的内容全丢了统计结果自然错误。这个问题的排查过程很有意思。我盯着代码看了很久觉得“统计逻辑明明是对的”后来随手在循环里打印读进来的字符串才发现第一行只读到了空格前的几个字母。这就是输入方式的问题。解决方法是直接用getline()读取整行而不是cin 。尤其当文本中可能有空格、制表符、标点时getline()几乎是唯一正确的选择。多说一句如果页面顶部用了ios::sync_with_stdio(false)那getline(cin, str)和标准 C 的gets混用会有风险。在 C 代码里要么全部用cin系要么全部用scanf/gets系不要混。4.3 第三版跨组计数没有清空算法和输入都改对了我又踩了第三个坑把计数器定义成全局数组后没有在每组数据开始前清空。第一组数据统计完计数数组里还残留大量字母然后直接进入第二组第二组的统计是在第一组残留基础上继续累加的。于是第一组结果对了第二组开始随机出错样本越靠后错得越离谱。排查方法也简单在每组输出前后打印一遍数组内容立刻看到计数在持续增长。解决方式是在每组处理开始时调用fill(cnt, cnt 26, 0)或者像我上面最终的代码那样在canForm函数入口处统一memset(cnt, 0, sizeof(cnt))。养成“函数入口清空全局状态”的习惯能避免很多隐蔽 bug。4.4 边界用例清单下面这份用例表建议在本地全部跑一遍确认输出正确后再提交。输入信 / 杂志预期结果为什么空行 / 任意文本Yes信里没有任何字母需求杂志再少也足够任意字母 / 空行No信有需求杂志一个字母都没有A a/aaYes大写 A 和小写 a 算同一个字母abc/cbaYes字母个数完全足够顺序无关aa/aNo信需要两个a杂志只有一个a1b2c3/abcYes数字不影响只看字母END作为结束标记处理时不输出结果它是结束标记不是一组样例这些用例覆盖了空字符串、大小写混合、非字母干扰、字母数量不足、字母顺序不同等关键情况。只要这些全过剩下的问题基本就只剩输入格式了。5. 从 Ransom Note 延伸出去的同型问题解完这道题最好做一件事把“统计频数”这个模型记牢因为它会在后续竞赛题里反复出现。这里简单列几个方向。5.1 LeetCode 383 几乎是同一道题LeetCode 的 Ransom Note 题目编号是 383题干跟 UVa 10580 高度相似也是给定两个字符串判断第一个字符串能不能由第二个字符串里的字符重新排列而成。区别只在于 LeetCode 版本默认只处理小写字母不需要过滤标点也不需要处理多组输入。做过 UVa 10580 再去做 383基本就是白送分。代码里只需要把 magazine 的字母逐个计数再检查 ransomNote 的每个字母是否够用即可。这类“模型相同、外壳不同”的题目最适合用来检验自己是否真正理解。如果你能不看任何题解把 383 做出来说明 UVa 10580 你已经掌握了。5.2 变位词与频率数组变位词anagram判断是另一个典型方向给定两个字符串判断它们能否通过重新排列变成一样的字符串。方法同样是统计每个字母出现次数然后比较两个频率数组。不同点只在于Ransom Note 比较的是“需求小于等于供应”变位词比较的是“完全相等”一个用一个用。基础逻辑完全同构。另外像“字符串能否重排成回文”“最多能删除几个字符使两个字符串相同”这类题本质上也会各种变形地用到频率统计。可以说Ransom Note 是这些题目的最小原型。5.3 从字母统计升级到单词统计再往上一层如果把题目改成“从杂志里剪单词来拼信”而不是剪字母那么统计单元就从字母变成了单词。这时 26 个计数器不够用因为单词的数量不可枚举。正确的做法是使用unordered_mapstring, int或字典树来统计每个单词的出现次数然后依然是“需求小于等于供应”的判断逻辑。这个升级过程非常自然理解完字母级频数法后再换成单词级只是换了一个容器整体思路不用重构。这也是很多面试题里会问到的扩展方向比如“给定一堆杂志单词和一个目标句子判断句子能不能由杂志单词组成”。最后聊点我自己的调试体会。UVa 10580 这种题看着简单但最耗时间的往往不是算法设计而是输入输出格式和边界情况。我前两版错误的代码花了大半个晚上才定位到根因后来养成一个习惯不管题目多简单提交前都会针对空行、大小写混合、非字母干扰、多组数据连续读取这四类情况各造一组测试数据。这个习惯让我在后面刷几百道题时少走了很多弯路。如果你也在入门阶段反复 WA别急着怀疑自己的算法先怀疑输入处理再把边界用例逐条过一遍往往问题就浮出水面了。