前端系列——查找字符串B的字符任意一种组合是否是字符串A的子串

摘要：例如，，则的其中一种组合是的子串，然后返回。如果从题目给出的例子来穷举，一共种组合，很容易穷举出来，但是字符串长度非常大的时候，怎么办呢所以，穷举的办法被我排除了。

这道算法题在前端面试中可能遇到，据说某条出过这题。

查找字符串B的字符任意一种组合是否是字符串A的子串。
例如 A=abc123，B=cba，则B的其中一种组合abc是A的子串，然后返回true。

题目的出处已经无从考究，接下来我们从JavaScript的角度来封装这样一个功能函数。

一开始看到这道题，你会想到什么？
我想到的是先列举出B的所有排列组合，存到数组里面，然后遍历，判断是否有组合包含在A中，如果有返回true，否则返回false。
如果从题目给出的例子来穷举，一共6种组合，很容易穷举出来，但是字符串长度非常大的时候，怎么办呢？
所以，穷举的办法被我排除了。

这名字听起来很奇怪，怎么个思路呢？

1、A的排序肯定是不变的，既然可变的我们很难下手，那么可以从不变的地方入手，以不变应万变。

2、看字符串可能不太习惯，我把A和B都转换成数组。

let a = A.split("") // [a, b, c, 1, 2, 3]
let b = B.split("") // [c, b, a]

3、先过滤数组为空的情况，如果a或者b为空，那么不需要比较，返回false。

if (a.length === 0 || b.length === 0) {
    return false
}

4、只看数组b，可以有6种排列组合，[c,b,a]，[a,b,c]，[a,c,b]，[b,a,c]，[b,c,a]，[c,a,b]。还记得第1步说的，我们不管b有多少种组合，都从a入手。

// a = [a, b, c, 1, 2, 3]
for (let j = 0; j < a.length; j++) { 

}

5、遍历a有什么作用呢？接下来我为大家揭晓何为标记删除法，允许我小小解释一下该方法，分为2个核心，“标记”和“删除”，“标记”是指标记当前数组a遍历的位置，“删除”是指删除数组b中的元素。

这样说可能不太懂，先不看代码，我用数组来模拟一下执行过程。

初始化的值
a = [a, b, c, 1, 2, 3]
b = [c, b, a]
==================================================
当遍历a的时候，j从0开始，遍历到a.length-1结束
==================================================
j = 0 // 给a里的字符加""，做个标记，表示当前遍历的下标位置
a = ["a", b, c, 1, 2, 3]
==================================================
然后我们发现数组b存在当前的字符"a"，执行删除操作
b = [c, b]
==================================================
j = 1 // 数组a遍历到第二个字符
a = [a, "b", c, 1, 2, 3] // 标记
b = [b] // 删除
==================================================
j = 1 // 数组a遍历到第三个字符
a = [a, b, "c", 1, 2, 3] // 标记
b = [] // 删除
==================================================
现在我们看到b数组变成空了，则证明b的任意一种排列存在于a中

6、上一步描述的情况是最简单的状态，刚好在A字符中存在不间断的字符组合。我们把A改一下，变成 A = a1b2c3abc。即使变复杂了，我们依旧可以使用标记删除发来做，只是稍微做一点处理。

初始化的值
a = [a, 1, b, 2, c, 3, a, b, c]
b = [c, b, a]
==================================================
当遍历a的时候，j从0开始，遍历到a.length-1结束
==================================================
j = 0 // 给a里的字符加""，做个标记，表示当前遍历的下标位置
a = ["a", 1, b, 2, c, 3, a, b, c]
==================================================
然后我们发现数组b存在当前的字符"a"，执行删除操作
b = [c, b]
==================================================
j = 1 // 数组a遍历到第二个字符
a = [a, "1", b, 2, c, 3, a, b, c] // 标记
// 突然发现第2个字符是1，现在该怎么办？我们只需要把数组b恢复初始状态即可

b = [c, b, a] // 恢复初始状态 
==================================================
接下来继续遍历，重复上面的处理步骤，直到数组b为空或者数组a遍历完成，返回结果

7、JavaScript代码实现
下面是第6步说明的代码实现，从代码中可以看到，不管B字符有多少排列组合，我们始终只需要遍历A的所有字符即可，内部实现也是用空间换时间。

// 遍历数组 a
    for (let j = 0; j < a.length; j++) {
        // 数组 b不为空，下一步
        if (b.length > 0) {
            // 数组a存在当前遍历的数组b的元素
            if (b.indexOf(a[j]) > -1) {
                // 删除b数组中匹配到的第一个对应下标的元素
                b.splice(b.indexOf(a[j]), 1)
                if (b.length === 0) {
                    // 如果数组b全部被删除了，则证明b是a的子串
                    return true
                }
            } else {
                // 数组b不存在当前遍历的数组b的元素，恢复b数组
                b = B.split("")
            }
        } else {
            // 数组 b为空返回true
            return true
        }
    }

与其他前端工程师的交流中，我还了解到了其他的解题思路，有些很有趣，比如考虑使用Map或Set、滑块区间比较等，不过我没有去用代码实现过，如果你有其他的方法，可以在下面留言交流。

评论区有人指出不能覆盖某些场景的测试用例，所以我对上面的具体过程做了改进，下面是改进后的源码。
增加了2个字段，isBack和isRestart，isRestart用来标记是否重新在当前位置遍历，isBack判断是否对数组遍历的下标进行回退一个单位。

var A = "abc123"
  , B = "cba"
function interface(A, B) {
    // 将A和B转成数组
    let a = A.split("")
    let b = B.split("")
    if (a.length === 0 || b.length === 0) {
        return false
    }
    let isBack = false, isRestart = 0
    // 遍历数组 a
    for (let j = 0; j < a.length; j++) {
        // 数组 b不为空，下一步
        if (b.length > 0) {
            isBack = false
            // 数组a存在当前遍历的数组b的元素
            if (b.indexOf(a[j]) > -1) {
                // 删除b数组中匹配到的第一个对应下标的元素
                b.splice(b.indexOf(a[j]), 1)
                if (b.length === 0) {
                    // 如果数组b全部被删除了，则证明b是a的子串
                    return true
                }
            } else {
                if (isRestart !== 0) {
                    isBack = false
                } else {
                    isBack = true
                }
                // 数组b不存在当前遍历的数组b的元素，恢复b数组
                b = B.split("")
                if (isBack) {
                    j -= 1
                    isRestart = 0
                }
                isRestart++
            }
        } else {
            // 数组 b为空返回true
            return true
        }
    }
    return false
}
interface(A, B)