5.4  如何判断两个字符串是否为换位字符串

5.4 如何判断两个字符串是否为换位字符串

【出自TX面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

换位字符串是指组成字符串的字符相同，但位置不同。例如：由于字符串“aaaabbc”与字符串“abcbaaa”就是由相同的字符所组成的，因此它们是换位字符。

分析与解答：

在算法设计中，经常会采用空间换时间的方法以降低时间复杂度，即通过增加额外的存储空间来达到优化算法性能的目的。就本题而言，假设字符串中只使用ASCII字符，由于ASCII字符共有266个（对应的编码为0～255），在实现的时候可以通过申请大小为266的数组来记录各个字符出现的个数，并将其初始化为0，然后遍历第一个字符串，将字符对应的ASCII码值作为数组下标，把对应数组的元素加1，然后遍历第二个字符串，把数组中对应的元素值-1。如果最后数组中各个元素的值都为0，说明这两个字符串是由相同的字符所组成的；否则，这两个字符串是由不同的字符所组成的。实现代码如下。

程序的运行结果如下：

aaaabbc和abcbaaa是换位字符

算法性能分析：

这种方法的时间复杂度为O（N）。