前端系列——查找字符串B的字符任意一种组合是否是字符串A的子串
风和日丽 2019-06-28
题目要求
这道算法题在前端面试中可能遇到，据说某条出过这题。
查找字符串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) 