登录
原创

JS基础算法(正则表达式 &递归篇)

专栏JS算法基础篇
发布于 2020-12-12 阅读 343
  • 前端
  • 面试
  • 算法
原创

1.重复的子字符串

给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。

示例 1:

输入: “abab”

输出: True

解释: 可由子字符串 “ab” 重复两次构成。

示例 2:

输入: “aba”

输出: False

示例 3:

输入: “abcabcabcabc”

输出: True

解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

用正则去做 /^(\w+)\1+$/即为对应正则表达式

export default (str)=>{
    var reg=/^(\w+)\1+$/
    return reg.test(str)
}

2.正则表达式匹配

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
'
’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
说明:
s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。

示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

示例 2:

输入:
s = “aa”
p = “a*”
输出: true
解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此,字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3:

输入:
s = “ab”
p = “."
输出: true
解释: ".
” 表示可匹配零个或多个(‘*’)任意字符(‘.’)。

示例 4:

输入:
s = “aab”
p = “cab”
输出: true
解释: 因为 ‘*’ 表示零个或多个,这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5:

输入:
s = “mississippi”
p = “misisp*.”
输出:

  • 一个字符一个字符对比,对比完一个扔掉一组,然后重复刚才的动作
  • 三种情况:无模式,有模式*,有模式.
export default (s,p)=>{
    let isMatch=(s,p)=>{
        // 边界情况,如果s和p都为空,说明处理结束,返回true,否则返回false
        if(p.length<=0){
            return !s.length
        }
        // 判断p模式字符串的第一个字符和s字符串的第一个字符是不是匹配
        let match=false
        if(s.length>0&&(p[0]===s[0]||p[0]==='.')){
            match=true
        }
        // p有模式的,字符后面有*
        if(p.length>1&&p[1]==='*'){
            // 第一种情况:s*匹配0个字符
            // 第二种情况:s*匹配1个字符,递归下去,用来表示s*匹配多个s
            return isMatch(s,p.slice(2))||(match && isMatch(s.slice(1),p))
        }else{// 字符后面没有*
            return match && isMatch(s.slice(1),p.slice(1))
        }
    }
    return isMatch(s,p)
}

3.复原IP地址

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
示例:
输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]
P由4部分构成,每部分范围0~255(递归)
所有情况都列出来(每个子字符串都可以是一位数到三位数),然后按条件筛选

export default (str)=>{
    // 保存所有符合条件的ip
    let r=[]
    // 递归函数
    let search=(cur,sub)=>{
        if(cur.length===4&&cur.join('')===str){
            r.push(cur.join('.'))
        }else{
            for(let i=0,len=Math.min(3,sub.length),tmp;i<len;i++){
                tmp=sub.substr(0,i+1)
                if(tmp<256){
                    search(cur.concat([tmp]),sub.substr(i+1))
                }
            }
        }
    }
    search([],str)
    return r
}

  • 递归的本质(就是一个while循环,但可以有多个条件或地方调用)
    • 每一个处理过程是相同的
    • 输入输出是相同的
    • 处理次数未知

4.与所有单词相关联的字符串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。

示例 1:

输入:
s = “barfoothefoobarman”,
words = [“foo”,“bar”]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 “barfoor” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2:

输入:
s = “wordgoodgoodgoodbestword”,
words = [“word”,“good”,“best”,“word”]
输出:[]

递归循环来计算出所有的words组合,然后匹配字符串即可。

export default (str,words)=>{
    // 保存结果
    let result=[]
    // 记录数组的长度,做边界条件计算
    let num=words.length
    // 递归函数体
    let range=(r,_arr)=>{
        if(r.length===num){
            result.push(r)
        }else{
            _arr.forEach((item,idx)=>{
                // 当前元素踢出去,留下剩下的
                let tmp=[].concat(_arr)
                tmp.splice(idx,1)
                range(r.concat(item),tmp)
            })
        }
    }
    range([], words)
    // [0,9,-1]
    return result.map(item=>{
        return str.indexOf(item.join(''))
    }).filter(item=>item!==-1).sort()
}

评论区

timing
3粉丝

励志做一条安静的咸鱼,从此走上人生巅峰。

0

0

0

举报