专注于 JetBrains IDEA 全家桶,永久激活,教程
持续更新 PyCharm,IDEA,WebStorm,PhpStorm,DataGrip,RubyMine,CLion,AppCode 永久激活教程

LeetCode 10. 正则表达式匹配

leetcode-cn.com/problems/re…

81_1.png

81_2.png

思路:动态规划

  • 这是一个通配符问题
  • .表示任意字符,*表示0个或多个字符,.*表示任何字符串除null外
  • 理解.*匹配ab, .*可以匹配..,每个点可以匹配任意字符,所以.*匹配ab
  • 通过动态规划来解决
  • dp[i+1][j+1]表示s中长度为i的子串与p中长度为j的子串是否匹配,这里s中长度为i的子串表示s.substring(0, i)
  • dp的长度 s.length + 1,p.length + 1
  • dp[0][0] = true,表示空串肯定匹配空串
  • 参考:www.youtube.com/watch?v=c5v…
  • 参考:www.youtube.com/watch?v=ym1…

81_3.png

这个是参考视频的画的图例

81_4.png

public boolean isMatch(String s, String p) {
    // 字符串为空返回false
    if (s == null || p == null) {
        return false;
    }
    boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
    // 这种情况s="",p=""返回true
    dp[0][0] = true;
    // 初始化p中类似a*这种模式
    for (int j = 0; j < p.length(); j++) {
        if (p.charAt(j) == '*' && dp[0][j - 1]) {
            dp[0][j + 1] = true;
        }
    }
    for (int i = 0; i < s.length(); i++) {
        for (int j = 0; j < p.length(); j++) {
            if (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.') {
                dp[i + 1][j + 1] = dp[i][j];
            }
            if (p.charAt(j) == '*') {
                // a*匹配空串
                if (p.charAt(j - 1) != '.' && p.charAt(j - 1) != s.charAt(i)) {
                    dp[i + 1][j + 1] = dp[i + 1][j - 1];
                } else {
                    // a*,可匹配 a,aa
                    // .*,可匹配 任意子串
                    dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i + 1][j] || dp[i][j + 1];
                }
            }
        }
    }
    return dp[s.length()][p.length()];
}

文章永久链接:https://tech.souyunku.com/43457

未经允许不得转载:搜云库技术团队 » LeetCode 10. 正则表达式匹配

JetBrains 全家桶,激活、破解、教程

提供 JetBrains 全家桶激活码、注册码、破解补丁下载及详细激活教程,支持 IntelliJ IDEA、PyCharm、WebStorm 等工具的永久激活。无论是破解教程,还是最新激活码,均可免费获得,帮助开发者解决常见激活问题,确保轻松破解并快速使用 JetBrains 软件。获取免费的破解补丁和激活码,快速解决激活难题,全面覆盖 2024/2025 版本!

联系我们联系我们