Leetcode 010. 正则表达式匹配

[meibin08]

题目描述:

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

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

匹配应该覆盖整个 字符串( s ) ，而不是部分字符串。

说明:

• s 可能为空，且只包含从 a-z 的小写字母。

• p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 * 。

示例 1:

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

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释:'*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

示例3:

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

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释:'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

提示：

• 0 <= s.length <= 20
• 0 <= p.length <= 30
• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有效的字符

难度：

• 难度：困难
• 支持语言：JavaScript、Java、Python、C++

相关标签

• 字符串
• 动态规划
• 回溯算法

相关企业

• 阿里
• 京东
• 腾讯

• 字节

复杂度分析

• 时间复杂度：O(mn)O(mn)，其中 mm 和 nn 分别是字符串 ss 和 pp 的长度。我们需要计算出所有的状态，并且每个状态在进行转移时的时间复杂度为 O(1)O(1)。
• 空间复杂度：O(mn)O(mn)，即为存储所有状态使用的空间。

思路 1（javascript）:

动态规划,dp[i][j]代表到索引[0,i]的p是否能被索引[0,j]的s匹配。

如果p[i]===s[j] || p[i]==='.'，说明它们匹配，dp[i][j]=dp[i-1][j-1]。

如果不匹配，但是p[i]==='*'，

1. 如果p的前一个能和当前s匹配并且dp[i][j-1]===true，说明*可以延长上一个的p来匹配当前的s；
2. 如果上面条件不符合，但是dp[i-2][j]===true，也就是说前2个的p能和当前s匹配，那么*可以作为数量0,相当与忽略前一个p。

思路 2:

• p[j−1]p[j - 1]p[j−1]为普通字符,若s[i−1]==p[j−1]s[i - 1] == p[j - 1]s[i−1]==p[j−1]，则dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i - 1][j - 1]dp[i][j]=dp[i−1][j−1]，否则匹配失败
• p[j−1]p[j - 1]p[j−1]为'.'，则dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i - 1][j - 1]dp[i][j]=dp[i−1][j−1]
• p[j−1]p[j - 1]p[j−1]为'*'：
  • (1)不看，则dp[i][j]=dp[i][j−2]dp[i][j] = dp[i][j - 2]dp[i][j]=dp[i][j−2]
  • (2)看，则dp[i][j]=dp[i−1][j]dp[i][j] = dp[i - 1][j]dp[i][j]=dp[i−1][j]

思路 3 py:

1. 先判断s和p的第一个字符是否匹配
2. 处理p[1]为*号的情况：匹配0个或多个字符
3. 处理.号的情况：匹配一个字符

思路 4 C++:

• 用指针的方法：
• 当*s和*p都空时，返回true
• 当*s不空，*p空时，返回false
• 当*s空，*p非空时，不一定，eg: p = "a*a*a*a*",最后一个*可以表示a出现0次
• '*'是关键因素，所以我们这里分*(p + 1) == '*'和*(p + 1) != '*'
• *(p + 1) != '*'，这种情况直接匹配当前字符，如果匹配成果，继续匹配下一个，匹配失败则返回false，
  所谓的匹配成功（1）相同字符（2）*p = '.'和*s != '\0'
• *(p + 1) == '*','*'可以表示0个及0个以上的字符：
  1. 匹配：（1）s不动，p后移两位（2）s后移一位，p不动
  2. 不匹配：s不动，p后移两位，跳过符号'*'

代码

JavaScript 实现

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
  let pLen=p.length,sLen=s.length
  let dp=Array(pLen+1).fill().map(()=>Array(sLen+1).fill(false))

  for(let i=0;i<pLen+1;i++){
    for(let j=0;j<sLen+1;j++){
      if(i===0 && j===0){
        dp[i][j]=true
      }else if(p[i-1]==="*" && j===0){
        dp[i][j]=dp[i-2][j]
      }
    }
  }
  for(let i=1;i<pLen+1;i++){
    for(let j=1;j<sLen+1;j++){
      let r=i-1,c=j-1
      if(p[r]===s[c] || p[r]==='.'){
        dp[i][j]=dp[i-1][j-1]
      }else if(p[r]==="*"){
        if(((p[r-1]===s[c] || p[r-1]===".") && dp[i][j-1]) || dp[i-2][j])
          dp[i][j]=true
      }
    }
  }
  return dp[pLen][sLen]
};

/**
  作者：arrowing
  链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/javascript-jie-fa-fei-zheng-ze-chao-yue-99-de-ti-j/
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    if (p.indexOf('*') === -1) { // 没有星号
        return isEqual(s, p)

    } else { // 有星号
        let splitArr = []
        let sIndex = 0
        let index

        // 第 1 步：将匹配模式串(p)格式化为有序的匹配串数组；
        while ((index = p.indexOf('*', sIndex)) > -1) {
            if (sIndex < index - 1) {
                splitArr.push( p.substring(sIndex, index - 1) )
            }
            splitArr.push( p[index - 1] + '*' )
            sIndex = index + 1
        }

        if (sIndex < p.length) {
            splitArr.push( p.substring(sIndex) )
        }

        // 第 2 步：将头尾不带星号的内容优先匹配（因为这部分内容必须完全匹配）；
        // 先去除头部
        let headStr = splitArr[0]
        if (headStr[1] !== '*') {
            if ( isEqual(s.substring(0, headStr.length), headStr) ) {
                s = s.substring(headStr.length)
                splitArr.shift()
            } else {
                return false
            }
        }

        // 再去除尾部
        let tailStr = splitArr[splitArr.length - 1]
        if (tailStr[1] !== '*') {
            if ( isEqual(s.substring(s.length - tailStr.length), tailStr) ) {
                s = s.substring(0, s.length - tailStr.length)
                splitArr.pop()
            } else {
                return false
            }
        }

        return recursionMatch(s, splitArr)
    }
};

/**
 * @param {string} s
 * @param {string[]} arr
 * @return {boolean}
 */
function recursionMatch (s, arr) {
    let item
    let index = -1

    for (let i = 0; i < arr.length; i++) {
        item = arr[i]

        // 第 3 步
        if (item[1] !== '*') { // 先处理不带星号的，因为必须要匹配到

            // 第 4 步
            if (item.indexOf('.') > -1) { // 不带星号，但是带点号
                let sLen = s.length
                let pLen = item.length
                if (pLen > s.length) {
                    return false
                } else {
                    let j = 0
                    while (j < sLen) {
                        if (isEqual(s.substring(j, j + pLen), item)) {
                            let result
                            if (j > 0) { // 匹配了，先消耗匹配值的左边内容
                                result = costStarArr(s.substring(0, j), arr.slice(0, i))
                            }

                            if (j === 0 || result === true) { // 消耗匹配值的剩余内容
                                let leftStr = s.substring(j + pLen)
                                let leftArr = arr.slice(i + 1)
                                result = recursionMatch(leftStr, leftArr)
                            }

                            if (result === true) {
                                return true
                            }
                        }
                        j++
                    }

                    // 带点号的内容匹配不到
                    return false
                }
            }

            // 第 5 步
            while ((index = s.indexOf(item, index + 1)) > -1) { // 各种可能性都进行匹配
                // console.log('recursionMatch:', s, arr, i, index)

                let result = costStarArr(s.substring(0, index), arr.slice(0, i)) // 匹配了，先消耗匹配值的左边内容

                // 第 6 步
                if (result === true) { // 左边内容成功消耗，看剩余内容是否能匹配
                    let leftStr = s.substring(index + 1)
                    let leftArr = arr.slice(i + 1)

                    if (leftStr.length) {
                        if (leftArr.length) {
                            let result = recursionMatch(leftStr, leftArr)
                            if (result === true) { // 剩余内容也匹配到了
                                return true
                            }
                        } else {
                            return false
                        }

                    // 第 8 步
                    } else { // 剩余可匹配内容为空
                        if (leftArr.length) { // 仍有可匹配数组
                            return leftArr.every(item => item[1] === '*')
                        }

                        return true
                    }
                }
            }

            // 第 7 步
            // 不带星号的内容匹配不到
            return false
        }
    }

    return costStarArr(s, arr)
}

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
function isEqual (s, p) {
    if (s.length !== p.length) {
        return false
    }

    let i = 0
    while ( i < s.length && (s[i] === p[i] || p[i] === '.') ) {
        i++
    }

    return s.length === i
}

/**
 * @param {string} s
 * @param {string[]} starArr
 * @return {boolean}
 */
function costStarArr (s, starArr) {
    if (s.length === 0) return true

    while (starArr.length) {
        let tmp = starArr.pop()
        if (tmp[0] === '.') {
            return true
        } else {
            let i = s.length - 1
            while (i >= 0) {
                if (s[i] === tmp[0]) {
                    i--
                } else { // 没匹配到
                    return costStarArr(s.substring(0, i + 1), starArr)
                }
            }
            return true
        }
    }

    return false
}

Java 实现

public boolean isMatch(String s, String p) {
    if (s == null || p == null)
        return false;
    int m = s.length();
    int n = p.length();
    boolean[][] dp = new boolean[m + 1][n+1];
    dp[0][0] = true;
    for (int i = 0; i < n; i++) {
        //如果p的第i+1个字符也就是p.charAt(i)是"*"的话，
        //那么他就可以把p的第i个字符给消掉（也就是匹配0次）。
        //我们只需要判断p的第i-1个字符和s的前0个字符是否匹
        //配即可。比如p是"a*b*"，如果要判断p的第4个字符
        //"*"和s的前0个字符是否匹配，因为字符"*"可以消去
        //前面的任意字符，只需要判断p的"a*"和s的前0个字
        //符是否匹配即可
        if (p.charAt(i) == '*' && dp[0][i - 1]) {
            dp[0][i + 1] = true;
        }
    }
    ……
}

// 作者：sdwwld
// 链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/dong-tai-gui-hua-he-di-gui-liang-chong-fang-shi-2/

class Solution {
public:
    bool isMatch(string s, string p) {
        return match(s.data(), p.data());
    }
    bool match(char* s, char* p) {
        if (!*p) return !*s;
        if (*(p + 1) != '*')
            return *s == *p || (*p == '.' && *s != '\0') ? match(s + 1, p + 1) : false;
        else
            return *s == *p || (*p == '.' && *s != '\0') ? match(s, p + 2) || match(s + 1, p) : match(s, p + 2);
            //或者return (*s == *p || (*p == '.' && *s != '\0')) && match(s + 1, p) || match(s, p + 2);
    }
};

// 作者：OrangeMan
// 链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/cjian-ji-dai-ma-ti-jie-ming-tian-xie-by-orangeman/

Python 实现

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p: return not s  # 结束条件

        first_match = (len(s) > 0) and p[0] in {s[0], '.'}
        # 先处理 `*`
        if len(p) >=2 and p[1] == '*':
            # 匹配0个 | 多个
            return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p))

        # 处理 `.` ，匹配一个
        return first_match and self.isMatch(s[1:], p[1:])


#作者：dz-lee
#链接：https://leetcode-cn.com/problems/regular-expression-matching/solution/jian-ming-qing-xi-xie-fa-python3xiang-xi-zhu-shi-b/

其他

• 原题leetcode链接：https://leetcode-cn.com/problems/regular-expression-matching/
• 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
• 说明：leetcode 题解 | 每日一题🔥 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。