前端系列——查找字符串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)

相关推荐