一、引言

来，跟我一起读：

anagram [‘ænə’græm] n. 回文构词法

希望这个单词的含义能够深入每一个读了这篇博客的人的心里：）弄懂了这个单词的含义，这道题也就懂了 80% 了。

接下来看看这道题：

Given two strings s and t, write a function to determine if t is an anagram of s.

For example, s = “anagram”, t = “nagram” , return true. s = “rat”, t = “car”, return false.

Note: You may assume the string contains only lowercase alphabets.

Follow up: What if the inputs contain unicode character? How would you adapt your solution to such case?

尽管或许只有几个单词比较晦涩，不过还是简单翻译下吧：

给定两个字符串 s 和 t，请写一个方法判断 t 是不是 s 的异构词。

注意： 你可以假定字符串只包含小写字母。

进一步： 如果输入含有 Unicode 字符怎么办？你将如何适配你的解决方案呢？

其实看例子就很容易懂题意了：

我们需要判断第二个参数字符串是否是第一个参数字符串的异构词

那么什么叫做异构词呢？根据简单的几个例子分析，我得出了以下三个判断条件：

两个字符串长度相同

含有字符种类相同

相同字符出现次数相同

至于下面的 Follow up我们之后再说，我们先来看看程序里如何进行上述总结的三个条件的判断吧。

二、std::unordered_map: 我们最忠实的朋友

看懂了题意，我很轻而易举的就想到了这么一个思路：

首先，统计 s 的所有字符的出现次数

然后，统计 t 的所有字符的出现次数

最后，遍历 s 的统计映射，按照指定的字符的出现次数是否跟 t 中的该字符的出现次数相同进行比较，全部都相同则返回 true，否则返回 false

这个方法很简单，但是注意这里有个思维漏洞：

万一 t 确实含有 s 中的所有字符并且出现次数相同，但是多包含了 s 中不存在的字符呢？

所以我们还需要在开头进行 s 与 t 的长度的判断。根据上述逻辑，代码如下：

// my solution 1 use unordered map , runtime = 16 ms class Solution1 { public: bool isAnagram(string s, string t) { if (s.size() != t.size()) return false; unordered_map<char, int> s_map, t_map; for (auto c : s) s_map[c]++; for (auto c : t) t_map[c]++; for (auto s_item : s_map) if (t_map[s_item.first] != s_item.second) return false; return true; } };

代码逻辑非常简单，只要熟悉 std::unordered_map 的基本使用方法的人都应该看得懂。这里之所以选择 std::unordered_map 是因为这里不需要排序，又需要 unordered map 的性能。

这个方法呢，使用了 C++ 11 的模板库，使用了映射的数据结构，完成了我们需要的 “指定字符出现次数计数”的功能。

可以说，这个方法中规中矩吧，但是达不到我心目中的那种极简的要求。

毕竟，我们追求的是：

更少的代码，更清晰的逻辑，以及可以接受的性能

三、std::sort: 竹杖芒鞋轻胜马，一蓑烟雨任平生

何必要统计字符的出现次数呢？

多麻烦呀~~~

所以我选择了 std::sort。

了解这个函数的同学肯定都了解， std::sort 可以按照字符的整型大小进行排序，更何况 std::string 还可以按照字典顺序进行比较。

简洁的代码如下：

// my solution 2 use sort , runtime = 22 ms class Solution2 { public: bool isAnagram(string s, string t) { sort(s.begin(), s.end()); sort(t.begin(), t.end()); return s == t; } };

这段代码只有短短 3 行，使用了两个 std::sort，最后一个比较返回结果。

逻辑更加清晰，代码量更加简少，虽然 runtime 确实比第一个方法多了 6 ms，但是我觉得可以接受。

毕竟，有时候开发的效率比程序的运行效率更重要。

四、高票答案：有趣的代码

尽管我写出了前面两个方案，但是我还是想看看高票答案们都用的什么方法，于是我就看到了这么一份代码：

public class Solution { public boolean isAnagram(String s, String t) { int[] alphabet = new int[26]; for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++; for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--; for (int i : alphabet) if (i != 0) return false; return true; } }

让我们忽略 Java 和 C++ 的语言上的区别：

首先，作者声明了 26 存储空间的 int 类型的数组 alphabet

然后，作者遍历 s 字符串，将其中的每一个字符都映射到 alphabet 的对应存储位中（第 1 个位置存储 a ,第二个位置存储 b，依次类推），只要出现一次，其存储位上的值就增加 1

再然后，作者同样遍历 t 字符串，作同样处理，只不过不同的是，指定位上的值，只要出现一次就减少 1

最后，作者再遍历一次 alphabet 数组，只要存在非 0 的值，则意味着 s 和 t 中存在出现次数不一样的字符，那么就可以判定二者非异构词；反之，如果全部为 0，则可以判定二者为异构词

这个方法非常清新脱俗有没有 !!!

巧妙的使用数组的下标对应了 26 个小写字母，再用对应的存储值对应了各个字母的出现次数，第一次遍历增加，第二次遍历递减，最后维持为 0 的必然为异构词。

妙！真妙！

五、Follow up: Unicode Characters?

虽然这道题提交成功了，但是我们或许还有一个地方没有考虑。

那就是题目的 Follow up:

Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case?

让我们一起考虑考虑，如何适配 Unicode 字符呢？

于是我编写了一个测试代码：

#include <iostream> #include <cstdlib> #include <unordered_map> #include <string> #include <algorithm> using std::cout; using std::endl; using std::unordered_map; using std::sort; using std::wstring; int main() { wstring s = L"你好"; wstring t = L"好你"; Solution4 solution; cout << solution.isAnagram(s, t) << endl; system("pause"); return 0; }

大家可以看到，我这里声明了宽字符版本的 std::wstring 类型的两个字符串，一个为 你好，另一个为 好你,然后我尝试调用我们的代码：

// my solution 3 for unicode characters class Solution3 { public: bool isAnagram(wstring s, wstring t) { sort(s.begin(), s.end()); sort(t.begin(), t.end()); return s == t; } }; // my solution 4 for unicode characters class Solution4 { public: bool isAnagram(wstring s, wstring t) { if (s.size() != t.size()) return false; unordered_map<char, int> s_map, t_map; for (auto c : s) s_map[c]++; for (auto c : t) t_map[c]++; for (auto s_item : s_map) if (t_map[s_item.first] != s_item.second) return false; return true; } };

其实上述两份代码，仅仅是将我前面讨论的两个方法的参数替换成了 std::wstring 而已，函数内部都没有改变；而通过我自己的调试，发现这两份代码依然可以运行，函数内部并没有受到参数是 Unicode 的影响。

为什么呢？

因为我们使用了 C++ 标准库：

在第一个方法里，我们使用的是 std::unordered_map，容器本身与底层类型无关，但是我们遍历的时候使用了 auto关键字，自己的“偷懒”习惯居然还增加了代码的鲁棒性

在第二个方法里，我们更加直接的使用了 std::sort，直接让标准库处理 Unicode 字符，可见并没有出现问题

综上所述，C++ 标准库的使用，不仅仅是提高了开发效率，也为很多情况下的兼容性作了深入的考虑，减少了开发者的很多工作。

六、总结

今天是高考的第一天。

想想高考已经过去了那么久了，依然还是有些慨然。想对那些孩子们说句衷心的祝福。不过想想现今大学生的现状，又深深感叹如果他们上了大学又开始了堕落，那么其实人生的路还有很多很多坎需要走呢。

人生不只高考这么一个坎需要走，尽管毕业了我们都还需要努力 ^_^

To be Stronger!