1. 从一道蓝桥杯真题看字符串处理的经典思路最近在整理蓝桥杯的历年真题翻到了ALGO-91这道“Anagrams问题”。这题本身不难但我觉得它特别有意思因为它几乎囊括了字符串处理中最基础、最核心的几个思想。很多朋友在刷题时可能会觉得这种题太简单看一眼就过了但恰恰是这些“简单”的题目最能检验你对基础概念的理解是否扎实以及你的代码实现是否足够严谨和高效。今天我就以这道题为例和大家深入聊聊字符串比较、字符计数、以及如何写出既清晰又高效的代码。所谓“Anagrams问题”简单来说就是判断两个单词是否互为“变位词”。变位词是指两个单词包含的字母种类和每个字母出现的次数完全相同只是字母的排列顺序不同。比如“listen”和“silent”就是一对经典的变位词。这道题就是给你两个字符串让你判断它们是否满足这个条件。题目本身没有复杂的算法但实现方式却可以有很多种每种方式背后都对应着不同的编程思维和效率考量。我们接下来就一步步拆解。2. 问题核心如何定义“字母组成完全相同”要判断两个字符串是否为变位词我们首先要明确“字母组成完全相同”在计算机里如何精确地量化。人眼可以一眼扫过去做模糊匹配但计算机需要明确的规则。这里有两个关键点字母的种类和每种字母的数量。第一忽略大小写。在大多数变位词的定义中是不区分大小写的。也就是说“Apple”和“apple”在字母组成上被认为是相同的尽管通常我们讨论的是单词但题目输入可能包含大小写。所以我们第一步通常是将两个字符串统一转换为全小写或全大写这是字符串比较前的标准预处理操作。第二只关心字母。原题描述中通常指的是英文字母但有时为了严谨我们需要考虑是否包含其他字符。在经典的变位词定义中通常只考虑字母并且忽略非字母字符如空格、标点。不过根据蓝桥杯ALGO-91的典型输入我们可以先假设输入就是纯字母字符串这样问题更聚焦。如果需要处理带空格的情况比如短语思路也是一样的先进行清洗过滤。那么如何比较种类和数量呢最直观的想法是排序。如果两个字符串排序后一模一样那它们必然是变位词。因为排序会将所有字母按统一顺序如字母表顺序排列如果组成相同排序结果必然相同。这个方法思路清晰代码简单。但它的时间复杂度是O(n log n)其中n是字符串长度。对于本题的规模这完全够用但它并不是时间复杂度最优的方法。更高效的方法是计数。我们可以统计每个字母26个小写字母在两个字符串中出现的次数。如果两个字符串对应的26个计数全部相等那么它们就是变位词。这个方法的时间复杂度是O(n)只需要遍历字符串两遍或一遍同时统计两个效率更高。下面我们就分别实现这两种方法并看看其中的细节和坑。3. 方法一排序比较法及其实现细节我们先来实现排序法。思路非常直接将两个字符串s1和s2转换为统一的小写形式。将转换后的字符串转换为字符数组。对两个字符数组分别进行排序。比较排序后的两个字符数组是否相等。以Java为例代码可能长这样import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); String s1 scanner.nextLine(); String s2 scanner.nextLine(); scanner.close(); // 1. 转换为小写 s1 s1.toLowerCase(); s2 s2.toLowerCase(); // 2. 转换为字符数组并排序 char[] arr1 s1.toCharArray(); char[] arr2 s2.toCharArray(); Arrays.sort(arr1); Arrays.sort(arr2); // 3. 比较排序后的数组 if (Arrays.equals(arr1, arr2)) { System.out.println(Y); } else { System.out.println(N); } } }这段代码看起来没问题但这里有几个初学者容易忽略的细节和潜在的坑坑点一长度不等时的快速判断。如果两个字符串长度不同它们绝对不可能是变位词。因为变位词要求每个字母的数量都相同总字母数自然相同。所以在排序或计数之前先判断一下if(s1.length() ! s2.length())如果不等直接返回“N”这是一个非常有效的优化可以提前结束很多不必要的计算。上面的代码没有做这个判断虽然不影响结果但不够高效。坑点二输入可能包含非字母字符。题目没有明确说明输入是否纯字母。如果输入是“a bc”和“cb a”它们包含空格。按照经典的变位词定义我们应该忽略空格。那么上面的代码就会出错因为空格也被转换成小写并参与了排序。所以更健壮的做法是在转换小写后使用replaceAll(“[^a-z]”, “”)这样的正则表达式移除非字母字符或者遍历字符手动过滤。在竞赛中一定要仔细阅读题目描述中的输入格式说明。坑点三关于Arrays.equals的使用。比较两个字符数组是否相等不能直接用arr1 arr2这比较的是引用地址。必须使用Arrays.equals(arr1, arr2)方法它会逐个比较数组元素。这是一个很基础但重要的点。排序法的优点是代码极其简洁逻辑一目了然。在面试或快速原型中如果你先说出这个方法并指出其O(n log n)的时间复杂度然后提出可以优化到O(n)的计数法会显得你思维有层次。但排序法因为要排序需要额外的空间字符数组并且时间复杂度不是最优。4. 方法二字符计数法——更优解的实现与优化现在来看更高效的计数法。核心是使用一个大小为26的整数数组作为计数器记录每个字母a-z出现的次数。具体步骤如果两个字符串长度不同直接返回“N”。将字符串统一转为小写。创建计数器数组int[] count new int[26]。遍历第一个字符串s1对于每个字符c执行count[c - ‘a’]。这里c - ‘a’将字符‘a’到‘z’映射到数组下标0到25。遍历第二个字符串s2对于每个字符c执行count[c - ‘a’]--。遍历计数器数组count如果所有元素都为0说明s1和s2中每个字母的出现次数完全一致输出“Y”否则输出“N”。这里有一个小技巧我们可以在第二步遍历s2时就进行提前判断。如果某个字符的计数在减1之后变成了负数说明s2中这个字符的出现次数已经超过了s1那么可以直接判定不是变位词无需继续遍历或检查整个数组。这又是一个微优化。Java实现代码如下import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); String s1 scanner.nextLine().toLowerCase(); String s2 scanner.nextLine().toLowerCase(); scanner.close(); // 快速判断长度不同则必然不是 if (s1.length() ! s2.length()) { System.out.println(N); return; } int[] count new int[26]; // 统计第一个字符串 for (int i 0; i s1.length(); i) { char c s1.charAt(i); // 严谨起见可以检查c是否在a-z之间但题目假设输入合法 count[c - a]; } // 遍历第二个字符串并检查 for (int i 0; i s2.length(); i) { char c s2.charAt(i); int index c - a; count[index]--; // 如果某个字母的计数变为负数说明s2中该字母比s1多直接失败 if (count[index] 0) { System.out.println(N); return; } } // 理论上如果长度相等且没有出现负数数组所有元素应该都为0 // 但为了绝对严谨可以再遍历一次检查是否全为0不过由于长度相等且未出现负数必然全为0 System.out.println(Y); } }这个实现的时间复杂度是O(n)空间复杂度是O(1)因为计数器数组大小固定为26与输入长度n无关。它比排序法更高效。注意c - ‘a’这个操作的前提是字符c确实是小写字母。如果输入可能包含非字母字符这个操作会导致数组下标越界产生负数或大于25的下标。因此在工业级代码或输入不确定的情况下必须添加合法性检查例如if (c ‘a’ c ‘z’)然后再进行计数。竞赛中如果题目保证输入合法则可以省略。5. 边界条件与代码健壮性探讨写算法题尤其是竞赛题通过样例只是第一步。能否处理好各种边界情况和异常输入才是区分代码质量的关键。对于这道题我们需要考虑以下几点1. 空字符串或null输入两个空字符串“”和“”应该是变位词字母组成都为空。一个空字符串和一个非空字符串肯定不是变位词。如果输入可能是null那么需要先判断避免调用toLowerCase()或length()时抛出NullPointerException。在蓝桥杯的系统里通常不会给出null输入但养成防御性编程的习惯是好的。2. 大小写混合与非字母字符如前所述这是最容易出错的地方。一个健壮的程序应该能处理“Hello”和“oLLeh”这样的输入它们是变位词吗按照忽略大小写的规则是的。也应该能决定是否处理“hello!”和“!olleh”如果忽略非字母它们是变位词如果考虑非字母感叹号!的数量不同则不是。这完全取决于题目要求。ALGO-91的官方描述通常指明是“单词”或“字符串”根据历年真题惯例一般只包含字母并且忽略大小写。但我们在思考时必须意识到这个前提。3. 超长字符串的性能虽然本题数据规模不大但思考一下如果字符串长度达到10^5甚至10^6我们的代码是否依然高效排序法O(n log n)可能会有点压力而计数法O(n)则游刃有余。这也是计数法更优的一个体现。此外对于计数法使用固定大小的int[26]数组在空间上也是绝对高效的。4. 字符集扩展如果问题不限于小写英文字母而是扩展到大写字母、数字甚至Unicode字符呢这时固定大小的数组就不适用了。我们可以使用HashMapCharacter, Integer来作为计数器。思路完全一样遍历第一个字符串在Map中增加计数遍历第二个字符串在Map中减少计数。最后检查Map中所有值是否都为0。这种方法可以处理任何字符集但空间和时间开销会比数组大一些。这是一个很好的扩展思考。6. 从解题到举一反三变位词问题的实际应用场景你可能觉得判断两个单词是不是变位词除了做题还有什么用其实这个看似简单的问题在现实世界的软件开发中有着不少有趣的应用。应用一文本分析与密码学。在简单的密码分析或文字游戏中寻找变位词是一种常见手段。例如在一些单词游戏或破译简单替换密码时识别出一组变位词可以帮助缩小可能单词的范围。因为变位词具有相同的字母频率分布。应用二数据清洗与归类。在大规模文本处理中比如构建搜索引擎的索引或进行文本聚类时我们可能需要将不同形式但字母组成相同的单词归为一类。例如有人可能将“Listen”误拼为“Listne”通过变位词检测系统可以提示可能的正确拼写或者将它们关联起来。应用三面试中的经典考题。“判断变位词”是面试中最高频的字符串面试题之一。面试官通过这道题可以考察候选人对基础数据结构的掌握数组、哈希表、对时间/空间复杂度的分析能力、对边界条件的考虑大小写、空格、非法字符以及代码的整洁度和健壮性。能够清晰阐述排序法和计数法并比较其优劣是一个很好的加分项。应用四算法设计思想的体现。这道题本质上是比较两个集合或多集合的相等性。排序法体现了“通过标准化排序再比较”的思想计数法则体现了“通过统计特征频率来比较”的思想。这两种思想在解决其他问题时也经常用到。比如比较两个列表是否包含相同元素忽略顺序就可以先排序再比较或者用哈希表统计元素频率。所以不要小看任何一道基础题。把它吃透理解其背后的原理、各种解法的权衡、以及可能的扩展你获得的将不仅仅是一道题的答案而是一类问题的解决方法论。7. 蓝桥杯备赛视角下的总结与练习建议回到蓝桥杯备赛本身。ALGO-91属于“算法训练”部分难度不高但它是构建你算法思维大厦的一块重要砖石。在备赛初期大量练习这类基础题至关重要。我的练习建议是独立实现不要只看懂思路就跳过一定要亲手在编码环境中敲出代码并运行通过。多种解法就像我们刚才做的对于一道题尽可能思考两种或以上的解法。比较它们的优缺点写在代码注释里。这能极大锻炼你的思维灵活性。测试用例自己设计测试用例。包括常规用例“listen”,“silent”、边界用例空字符串、单个字符、长字符串、特殊用例大小写混合“Hello”/“oleHl”、包含空格“a bc”/“cb a”。用这些用例去测试你的程序确保其健壮性。触类旁通在蓝桥杯练习系统或其他OJ上搜索“Anagrams”或“变位词”相关的题目进行集中练习。你会发现题目可能会变换形式比如“在一组字符串中找出所有变位词分组”其核心仍然是我们今天讨论的计数比较法。最后关于代码风格。在竞赛中在保证正确和效率的前提下代码应尽量简洁、清晰。变量名使用有意义的名称如count在关键步骤加上简短注释。像这道题一个Main类一个main方法配合Scanner输入结构清晰就是很好的竞赛代码风格。这道“Anagrams问题”就像一把钥匙帮你打开了字符串处理与哈希计数思想的大门。把它理解透彻后续遇到更复杂的字符串问题比如子串、模式匹配、字符串编码时你会有更扎实的基础和更清晰的思路。