正则表达式常见的两种算法题

重复的子字符串

给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成,给定的字符串只含有小写英文字母,并且长度不超过10000
示例1:
输入:“abcb”
输出:True
解释:可由字符串“ab”重复两次构成
示例2:
输入:“aba”
输出:False
示例3:
输入:“abcabcabcabc”
输出:True
解释:可由字符串“abc”重复四次构成(或“abcd”重复两次)

\1代表重复匹配了1次以上

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

测试用例

import subLoopStr from '../../code/regexp/lesson1'

test('subLoopStr', () => {
  expect(subLoopStr('abab')).toBe(true)
})
test('subLoopStr:2', () => {
  expect(subLoopStr('abababc')).toBe(false)
})

自定义正则匹配规则

给定一个字符串(s)和一个字符模式(p)。实现支持‘.’和‘*’的正则表达式匹配

‘.’匹配任意单个字符
‘*’匹配零个或多个前面的元素

匹配应该覆盖整个字符串(s),而不是部分字符串
说明:

  • s可能为空,且只包含从a-z的小写字母
  • p可能为空,且只包含从a-z的小写字母,以及字符.和*
    示例1:
    输入:
    s=“mississippi”
    p=“misisp*”
    输出:false
export default (str, mode) => {
  // 对模式变量进行正则筛选
  let modeArr = mode.match(/([a-z.]\*)|([a-z]+(?=([a-z.]\*)|$))/g)
  // 光标位置从0开始
  let cur = 0
  let strLen = str.length
  for (let i = 0, len = modeArr.length, m; i < len; i++) {
    // 对于模式分为三类,.*|a*|cdef
    m = modeArr[i].split('')
    // 如果第二位是*表示是有模式的
    if (m[1] === '*') {
      if (m[0] === '.') {
        cur = strLen
        break
      } else {
        // 看光标位置的字符串是否等于m的第一位,如果是,光标右移
        while (str[cur] === m[0]) {
          cur++
        }
      }
    } else {
      for (let j = 0, jl = m.length; j < jl; j++) {
        if (m[j] !== str[cur]) {
          return false
        } else {
          cur++
        }
      }
    }
  }
  return cur === strLen
}

测试用例

import regModeStr from '../../code/regexp/lesson2'

test('regModeStr', () => {
  expect(regModeStr('aaa', 'caa*')).toBe(false)
})
test('regModeStr:2', () => {
  expect(regModeStr('aaabc', 'a*bc')).toBe(true)
})
test('regModeStr:3', () => {
  expect(regModeStr('aaabc', 'a*.*')).toBe(true)
})
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容