UVa 1509 Leet

题目描述Leet\texttt{Leet}Leet语言是一种互联网上常用的替代英语字母表。每个英文字符可以被一个或多个相似的Leet\texttt{Leet}Leet字符替换。例如ACMICPC可以写成4(|V|1(|(其中A→4C→(M→|V|I→1P→|。本题要求判断给定的标准英语短语和 Leet 短语是否相同遵循以下规则规则a\texttt{a}a每个英文字符最多映射到kkk个Leet\texttt{Leet}Leet字符1≤k≤31 \leq k \leq 31≤k≤3。规则b\texttt{b}b每个英文字符在同一个短语中只能使用一种映射方式但不同英文字符可以映射到相同的Leet\texttt{Leet}Leet字符序列。输入格式第一行测试用例数TTT。每个测试用例第一行整数kkk1≤k≤31 \leq k \leq 31≤k≤3。第二行标准英语短语小写字母a~z长度111~151515。第三行Leet\texttt{Leet}Leet短语长度≥1\geq 1≥1包含可打印符号大小写字母、数字、、\、/、-、、^、|、[、]、(、)、{、}、、。输出格式每个测试用例输出一行如果两个字符串相同输出111。否则输出000。题目分析问题本质这是一个带约束的字符串匹配问题。我们可以将问题抽象为给定模式串SSS标准英语短语和文本串TTTLeet\texttt{Leet}Leet短语每个模式字符S[i]S[i]S[i]可以匹配文本串中一个长度为111到kkk的子串且同一个模式字符在整个匹配过程中必须匹配相同的子串映射一致性要求判断能否用SSS完整匹配TTT。约束条件分析长度限制k≤3k \leq 3k≤3非常小意味着每个英文字符最多扩展成333个Leet\texttt{Leet}Leet字符。映射一致性这是本题的核心难点。例如如果决定a映射为那么后面所有a都必须映射为。映射冲突不同英文字符可以映射到相同字符串例如b和c都可以映射为|但同一个字符不能有两种映射。数据规模标准短语长度≤15\leq 15≤15Leet\texttt{Leet}Leet短语长度无明确上限但由于k≤3k \leq 3k≤3Leet\texttt{Leet}Leet短语长度最多约为454545。示例分析示例111k3标准mississippi Leetnni55i55ippi可能的映射m→nni→is→55p→pp检查mississippi按上述映射得到nni55i55ippi匹配成功。示例222k2标准foobar Leet|o08ar无法找到合法映射输出000。解题思路算法选择由于需要尝试所有可能的映射组合且状态空间有限我们采用深度优先搜索DFS\texttt{DFS}DFS 回溯的方法。同时使用记忆化可选来避免重复状态。状态定义在DFS\texttt{DFS}DFS过程中我们需要记录posEng当前匹配到标准短语的第几个字符从000开始。posLeet当前匹配到 Leet 短语的第几个字符从000开始。mapping一个哈希表记录每个英文字符已经确定的映射字符串。递归边界成功状态posEng engLen且posLeet leetLen说明两个字符串都被完整匹配。失败状态其中一个到达末尾而另一个未到或者当前字符无法匹配。递归过程对于当前标准字符curChar eng[posEng]情况111curChar已经有映射取出映射字符串mapped检查 Leet 串从posLeet开始的子串是否等于mapped如果相等继续递归dfs(posEng 1, posLeet mapped.length())如果不相等此路不通情况222curChar还没有映射尝试所有可能的映射长度len从111到kkk取 Leet 子串candidate leet.substr(posLeet, len)将curChar - candidate加入映射表递归dfs(posEng 1, posLeet len)递归返回后回溯从映射表中删除curChar为什么不需要禁止不同字符映射到相同串规则b\texttt{b}b明确允许不同英文字符映射到相同的Leet\texttt{Leet}Leet字符串因此我们在尝试新映射时不需要检查该子串是否已被其他字符使用。复杂度分析标准短语长度n≤15n \leq 15n≤15每个字符最多尝试kkk种长度k≤3k \leq 3k≤3每个字符在无映射时最多尝试kkk次有映射时只需111次检查最坏时间复杂度O(kn)O(k^n)O(kn)当n15,k3n15, k3n15,k3时315≈1.4×1073^{15} \approx 1.4 \times 10^7315≈1.4×107可接受。优化建议本题可选使用记忆化dp[posEng][posLeet]记录当前状态是否已经搜索过避免重复计算。但由于nnn很小且字母映射状态复杂记忆化实现较麻烦本题直接DFS\texttt{DFS}DFS即可通过。代码实现// Leet// UVa ID: 1509// Verdict: Accepted// Submission Date: 2026-05-23// UVa Run Time: 0.590s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intT,k;string eng,leet;unordered_mapchar,stringmp;// 英文字符 - Leet映射boolok;voiddfs(intposEng,intposLeet){if(ok)return;// 已经找到答案提前返回if(posEngeng.length()posLeetleet.length()){oktrue;// 完全匹配成功return;}if(posEngeng.length()||posLeetleet.length())return;// 边界越界charcurChareng[posEng];if(mp.count(curChar)){// 当前字符已有映射stringmappedmp[curChar];if(leet.substr(posLeet,mapped.length())mapped)dfs(posEng1,posLeetmapped.length());}else{// 当前字符无映射尝试所有可能的映射长度for(intlen1;lenk;len){if(posLeetlenleet.length())break;// 长度不够string candidateleet.substr(posLeet,len);mp[curChar]candidate;// 建立映射dfs(posEng1,posLeetlen);mp.erase(curChar);// 回溯撤销映射}}}intmain(){cinT;while(T--){cinkengleet;mp.clear();okfalse;dfs(0,0);cout(ok?1:0)endl;}return0;}总结本题的核心在于理解映射一致性的约束并通过DFS\texttt{DFS}DFS回溯枚举所有可能的映射方案。由于k≤3k \leq 3k≤3且标准短语长度≤15\leq 15≤15搜索空间可控直接搜索即可通过。代码实现时需要注意回溯的正确性每次尝试新映射后必须撤销以免影响其他分支。边界条件注意字符串下标越界问题。提前剪枝一旦找到答案立即返回避免不必要的搜索。