利用”若A+B=X+Y, A*B=X*Y，那么A=X, B=Y或A=Y,B=X“判断两字符串是否互为排列组合

题目

如题：

给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例 1：

1 2	输入:s1 = "abc",s2 = "bca" 输出: true

示例 2：

1 2	输入:s1 = "abc",s2 = "bad" 输出: false

该题的解题思路很多，如数组计数、哈希集合、排序等。本文讲解一种巧用数学公式的解法。

有趣的推理

首先，我们来推导一个公式，已知以下两个等式：

$$
A+B=X+Y\
AB=XY
$$

其中A,B, X, Y不为0。我们的目标是证明：A，B和X，Y两两相等，即$A=X,B=Y$ 或者$A=Y,B=X$。

推导过程如下：

对已知的第一个等式进行移向，可以得到

$$
B=Y−A+X
$$

将B带入到第二个等式，可得

$$
A(Y−A+X) = XY
$$

经过代数运算，可得

$$
AY-A^2+AX = XY\
A(X-A) = (X-A)Y\
$$

所以可得

$$
X=A, Y=B
$$

或者

$$
Y=A, X=B
$$

证明完毕。

$A=X,B=Y$ 或者$A=Y,B=X$，这意味着A,B 和X,Y这两对数字是全排列组合，数字都是相同的，只是打乱的顺序。

有了这个推理，根据加法和乘法的交换律和结合律，我们可以继续增加变量，得出这么一个结论：

若A1 + A2 + A3 + … +An = B1 + B2+ B3 + … + Bn，那么A1到An和B1到Bn肯定一一对应，即是全排列组合。

字符串排列组合

知道了上述的推理，和我们的题目有什么关系呢？

题目是要我们证明两个字符串是否是全排列组合，我们是否可以利用刚才得到的全排列性质来解题呢？

答案是可以的，思路是这样的：如果我们把每个字符都看成一个不重合的数字，通过遍历字符串，对字符映射成的数字进行A+B和A*B的计算，只要两个字符串得出的结果一样，就说明这两个字符串互为全排列组合，即其中一个字符串的字符重新排列后是另一个字符串。

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var CheckPermutation = function(s1, s2) {
    if(s1.length !== s2.length) return false
    const [s11, s22] =[s1.toLowerCase(),s2.toLowerCase()]
    let sum1 = 0, sum2 = 0, multi1 = 1, multi2 = 1;
    for(let i=0;i<s11.length;i++){
        sum1 += s11[i].charCodeAt(0)-'a'.charCodeAt(0)+1
        sum2 += s22[i].charCodeAt(0)-'a'.charCodeAt(0)+1

        multi1 *= s11[i].charCodeAt(0)-'a'.charCodeAt(0)+1
        multi2 *= s22[i].charCodeAt(0)-'a'.charCodeAt(0)+1
    }
    return sum1 === sum2 && multi1 === multi2
};

// case1: s1="abc", s2="bca", 输出true，预期true
// case2: s1="abc", s2="bad", 输出false，预期false
// case3: s1="aac", s2="bbb", 输出false，预期false
// case4: s1="abbcdde", s2="abcccde", 输出false，预期false
// case5: s1="bkhfhqlayvlhdqmxvnkqvtkojouugfsnwmyoywkilsnubnkvhdbrltuxvoblurpfinpigajttcvkcxlylblcaocsjmwdvwepvnfr", 
// s2="mtycyvobjldulmhsuqvtrhqnisjkuxhvaxqkvpbllnkvvakxjbolefpyrtiivvwctunasbbocldflkcknmwgofngorduwlwhyfnp" false
// 输出false，预期true

可以看到，这个算法在执行第5个case的时候出错了，这是因为字符串的长度很长，我们的字符映射是从1-26，相乘很容易遇到溢出的问题，导致计算不准确。

但是好消息是上述解法证明我们的推理没有问题，思路没有问题，接下来我们思考如何解决计算溢出导致失去精度问题。

位运算：解决溢出

我们引入位向量，什么是位向量呢？

位向量（bit vector），是一个仅包含0和1的数组或者序列，其中每一位都代表某个元素的状态或属性。例如，1表示存在，0表示不存在。位向量表示方法非常高效，可以在固定大小的数组中存储大量的信息，而且位向量可以适合进行位运算，可以提高计算效率。

例如我们可以用以下位向量表示0-5这几个数字：

0 --> 1
1 --> 10
2 --> 100
3 --> 1000
4 --> 10000
5 --> 100000

数字和位向量的关系为：数字表示位向量中为1的位置（从右往左看）。值得注意的是**，位向量的创建需要自己赋予含义，并不是固定的。**

由于数字和字母之间可以通过ASCII码联系起来，例如a对应97，b对应98，c对应99，所以我们也可以约定一些位向量来表示字母，例如

a --> 0 --> 1
b --> 1 --> 10
c --> 2 --> 100
...
y --> 24 --> 1000000000000000000000000
z --> 25 --> 10000000000000000000000000

可以发现此处我们做了相对处理，把a看成0，而不是97，这样可以节省空间，只需要26位就可以表示26个字母。

利用**左移运算，**可以创建上述位向量：

1 << 0 = 1
1 << 1 = 10
1 << 2 = 100
1(十进制） << 3(十进制） = 1000(二进制）

1 << ('a'.charCodeAt(0)-'a'.charCodeAt(0)) = 1
1 << ('b'.charCodeAt(0)-'a'.charCodeAt(0)) = 10
1 << ('c'.charCodeAt(0)-'a'.charCodeAt(0)) = 100
1 << ('d'.charCodeAt(0)-'a'.charCodeAt(0)) = 1000

加法和乘法有这样的规律：

交换律
任何数字和0 相加，等与自身
任何数字和1相乘，等于自身

在位运算中，和加法和乘法规律非常相似的运算是位运算的**加法和异或。**加法比较简单，任何进制的加法都是一样的规律，而且相等，也就是二进制的x肯定等于n进制的y。我们重点来看看异或。

异或的运算逻辑如下：

1 ^ 1 = 0

1 ^ 0 = 1

0 ^ 1 = 1

0 ^ 0 = 0

简单来说，异或的特性是，两个值相同，结果为0，不同则结果为1。异或运算具有一定定律：

任何值与自身异或，结果为0

x ^ x = 0

任何值与0异或，结果为其自身

x ^ 0 = x

交换律

1	x ^ y ^ z = x ^ z ^ y

结合律

1	x ^ y ^ z = x ^ (y ^ z)

除了第一条，其他都和乘法非常类似。所以我们用位运算来改进我们上述算法。

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var CheckPermutation = function(s1, s2) {
  if(s1.length !== s2.length) return false
    const [s11, s22] =[s1.toLowerCase(),s2.toLowerCase()]
  let [bitSum1, bitSum2] = [0,0]
  let [bitMulti1, bitMulti2] = [0,0]
  for(let i=0;i<s11.length;i++){
    bitSum1 += 1 << (s11[i].charCodeAt(0)-'a'.charCodeAt(0))
    bitSum2 += 1 << (s22[i].charCodeAt(0)-'a'.charCodeAt(0))

    // 异或的两条规律：交换率和任何值与自身异或，结果为0
    bitMulti1 ^= 1 << (s11[i].charCodeAt(0)-'a'.charCodeAt(0))
    bitMulti2 ^= 1 << (s22[i].charCodeAt(0)-'a'.charCodeAt(0))
  }
  return bitSum1 === bitSum2 && bitMulti1 === bitMulti2
};

// case1: s1="abc", s2="bca", 输出true，预期true
// case2: s1="abc", s2="bad", 输出false，预期false
// case3: s1="aac", s2="bbb", 输出false，预期false
// case4: s1="abbcdde", s2="abcccde", 输出false，预期false
// case5: s1="bkhfhqlayvlhdqmxvnkqvtkojouugfsnwmyoywkilsnubnkvhdbrltuxvoblurpfinpigajttcvkcxlylblcaocsjmwdvwepvnfr", 
// s2="mtycyvobjldulmhsuqvtrhqnisjkuxhvaxqkvpbllnkvvakxjbolefpyrtiivvwctunasbbocldflkcknmwgofngorduwlwhyfnp" false
// 输出true，预期true

算法复杂度分析

时间复杂度分析

字符串长度为 n，因此循环的次数是 O(n)。
在循环内部，主要执行了一些位运算和常数时间的操作，这些操作的时间复杂度可以视为 O(1)。
因此，整个算法的时间复杂度为 O(n)。

空间复杂度分析

使用了一些常量空间变量（例如，bitSum1、bitSum2、bitMulti1、bitMulti2）和循环变量（例如，i）。
不随输入规模 n 的增长而变化，因此是 O(1) 的空间复杂度。

总结

时间复杂度：O(n)
空间复杂度：O(1)

总的来讲，这个算法基于一则数学推理，采用了一种巧妙的位运算方法来判断两个字符串是否为排列。相比于其他解题思路，例如排序，暴力解法，等，本文章的解题思路更加高效。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。