学点算法之字符串的乱序检查

问题

字符串的乱序检查。

一个字符串是另一个字符串的乱序。如果第二个字符串只是第一个的重新排列，例如，’heart’ 和 ‘earth’ 就是乱序字符串。’python’ 和 ‘typhon’ 也是。为了简单起见，我们假设所讨论的两个字符串具有相等的长度，并且他们由 26 个小写字母集合组成。我们的目标是写一个布尔函数，它将两个字符串做参数并返回它们是不是回文。

解法1:检查

我们对乱序问题的第一个解法是检查第一个字符串是不是出现在第二个字符串中。如果可以检验到每一个字符，那两个字符串一定是回文。可以通过用 None 替换字符来完成检查。但是，由于 Python 字符串是不可变的，所以第一步是将第二个字符串转换为列表。第一个字符串中的每个字符可以通过检查在第二个列表中检查元素是否存在，如果存在，替换成 None。

s1 的每个字符都会在 s2 中进行最多 n 个字符的迭代

s2 列表中的 n 个位置将被访问一次来匹配来自 s1 的字符。访问次数可以写成 1 到 n 整数的和，可以写成

当 n 变大，n^2 这项占据主导，1/2 可以忽略。所以这个算法复杂度为 O(n^2 )。

解法2:排序和比较

另一个解决方案是利用这么一个事实，即使 s1,s2 不同，它们只有由完全相同的字符组成，它们才是回文。所以，如果我们按照字母顺序排列每个字符串，从 a 到 z，如果两个字符串相同，则这两个字符串为回文。

这个算法比较简单，只用到了排序算法，那么排序算法的复杂度还是多少呢？

在这里找到了答案

python中的sorted算法，网上有人撰文，说比较低级。其实不然，通过阅读官方文档，发现python中的sorted排序，真的是高大上，用的Timsort算法。什么是Timsort，请看 wiki的解释：http://en.wikipedia.org/wiki/Timsort

另外，国内有一个文档，适当翻译：http://blog.csdn.net/yangzhongblog/article/details/8184707，这里截取一个不同排序算法比较的图示，就明白sorted的威力了。

从时间复杂度来看，Timsort是威武的。

从空间复杂度来讲，需要的开销在数量大的时候会增大。

解法3: 穷举法

解决这类问题的强力方法是穷举所有可能性。

对于回文检测，我们可以生成 s1 的所有乱序字符串列表，然后查看是不是有 s2。这种方法有一点困难。当 s1 生成所有可能的字符串时，第一个位置有 n 种可能，第二个位置有 n-1 种，第三个位置有 n-3 种，等等。总数为 ， 即 。

虽然一些字符串可能是重复的，程序也不可能提前知道这样，所以他仍然会生成 个字符串。

事实证明，n! 比 n^2 增长还快，事实上，如果 s1 有 20个字符长，则将有 个字符串产生。如果我们每秒处理一种可能字符串，那么需要 年才能过完整个列表。

所以当然不会采取这种方案了。

解法4: 计数和比较

我们最终解决回文的方法是利用两个乱序字符串具有相同的 a, b, c 等等的事实。

我们首先计算的是每个字母出现的次数。由于有 26 个可能的字符，我们就用 一个长度为 26 的列表，每个可能的字符占一个位置。每次看到一个特定的字符，就增加该位置的计数器。最后如果两个列表的计数器一样，则字符串为乱序字符串。

同样，这个方案有多个迭代，但是和第一个解法不一样，它不是嵌套的。两个迭代都是 n, 第三个迭代，比较两个计数列表，需要 26 步，因为有 26 个字母。一共 T(n)=2n+26T(n)=2n+26，即 O(n)，我们找到了一个线性量级的算法解决这个问题。

如果让我自己来选择，我可能会选第二种，第二种最简单，也最好理解。但是最后的结论表明解法4才是最优解法，排序固然简单，但是但数量很大的时候，可能远不止我们想的那么简单。

在结束这个例子之前，我们来讨论下空间花费，虽然最后一个方案在线性时间执行，但它需要额外的存储来保存两个字符计数列表。换句话说，该算法牺牲了空间以获得时间。

很多情况下，你需要在空间和时间之间做出权衡。这种情况下，额外空间不重要，但是如果有数百万个字符，就需要关注下。作为一个计算机科学家，当给定一个特定的算法，将由你决定如何使用计算资源。

如有错误，请指出

图片来源

各位下期见，不聊了，又该搬砖了。。。