资讯专栏INFORMATION COLUMN

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

hsluoyz / 1176人阅读

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

题目要求

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

查找字符串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)

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/52996.html

相关文章

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

    摘要:例如,,则的其中一种组合是的子串,然后返回。如果从题目给出的例子来穷举,一共种组合,很容易穷举出来,但是字符串长度非常大的时候,怎么办呢所以,穷举的办法被我排除了。 题目要求 这道算法题在前端面试中可能遇到,据说某条出过这题。 查找字符串B的字符任意一种组合是否是字符串A的子串。例如 A=abc123,B=cba,则B的其中一种组合abc是A的子串,然后返回true。 算法思路 题目的...

    zengdongbao 评论0 收藏0
  • JavaScript正则表达式

    摘要:正则表达式是由普通字符例如字符到以及特殊字符称为元字符组成的文字模式。方法参数一个正则表达式对象。如果正则表达式没有标志,则会返回和相同的结果。其被视为一整个字符串,而不是一个正则表达式。 正则表达式 正则表达式(Regular Expression)是一种文本模式,包括普通字符(例如,a 到 z 之间的字母)和特殊字符(称为元字符)。正则表达式使用单个字符串来描述、匹配一系列匹配某个...

    jsdt 评论0 收藏0
  • Python中正则表达式

    摘要:正则表达式就是用来描述他称为正则集的代数的表达式,因此采用正则表达式这个术语。文本中正则表达式结束搜索的索引值与和方法的同名参数相同。对象是一个编号的正则表达式通过提供的一系列方法可以对文本进行匹配查找。 一、概述 今天这篇文章带领大家学习一下Python中的正则表达式,当然了,正则表达式本身的内容就足以写好几本书了,我们这里列出的内容,仅仅是Python中常用的和基础的一些内容。 那...

    Juven 评论0 收藏0
  • JavaScript必会技能——正则表达式

    摘要:语法参数必填项,字符串或正则表达式,该参数指定的地方分割可选该参数指定返回的数组的最大长度,如果设置了该参数,返回的子字符串不会多于这个参数指定的数组。该数组通过在指定的边界处将字符串分割成子字符串。把正则表达式拆分成小表达式。 正则表达式是什么 RegExp 对象表示正则表达式,它是对字符串执行模式匹配的强大工具。 为什么使用正则表达式 测试字符串内的模式。例如,可以测试输入字符串...

    FrozenMap 评论0 收藏0
  • JavaScript正则表达式

    摘要:引用就是允许在同一个正则表达式的后部引用前面的子表达式。这个数字制定了带圆括号的子表达式在正则表达式中的位置。对正则表达式中前一个子表达式的引用,并不是指对子表达式模式的引用,而是指与那个模式匹配的文本的引用。 前言 本文主要是在读《JavaScript高级程序语言设计》一书有关正则表达式的章节的知识点记录,方便后续查阅。 什么是正则表达式 正则表达式是用来描述字符组合的某种规则。它可...

    sixleaves 评论0 收藏0

发表评论

0条评论

hsluoyz

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<