共计 3105 个字符，预计需要花费 8 分钟才能阅读完成。
题目要求
这道算法题在前端面试中可能遇到，据说某条出过这题。
查找字符串 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)
