首页 > 代码库 > LeetCode - 10 - Regular Expression Matching
LeetCode - 10 - Regular Expression Matching
题目
URL:https://leetcode.com/problems/regular-expression-matching
解法
动态规划。
- p[i - 1] == s[i - 1], dp[i][j] = dp[i - 1][j - 1]:字符匹配,如 ‘a‘ 匹配 ‘a‘,两个字符匹配的情况下,看两个字符之前字符的匹配情况。
- p[i - 1] = ‘.‘, dp[i][j] = dp[i - 1][j - 1]: ‘.‘ 匹配,如 ‘.‘ 匹配 ‘a‘,两个字符匹配的情况下,要看两个字符之前字符的匹配情况。
- p[i - 1] = ‘*‘: ‘*‘匹配,具体如下。
‘*‘ 匹配包括三种情况:
- dp[i][j] = dp[i][j - 2]:‘*‘ 配空字符,如 "" 匹配 "a*"。对于 p,需要回退有关 ‘*‘ 和与 ‘*‘ 组合的字符,再看字符的匹配情况。
- p[i - 1] == s[i - 1] || s[i - 1] = ‘.‘, dp[i][j] = dp[i - 1][j - 2] || 上一个情况:‘*‘ 匹配一个字符,如 "a" 匹配 "a*"。对于 s 和 p,s 需要回退当前字符,需要回退有关 ‘*‘ 和与 ‘*‘ 组合的字符。假设匹配字符失败,那么 ‘*‘ 可能是匹配空字符,需要判断空字符的情况。
- p[i - 1] == s[i - 1] || s[i - 1] = ‘.‘, dp[i][j] = dp[i - 1][j] || 上两个情况:‘*‘ 匹配多个字符,如 "aaa" 匹配 "a*",对于 s 来说,s 需要回退当前字符,p 需要留下当前字符与之前的情况进行匹配。
初始状态也需要考虑:
- dp[0][0] 肯定为 true。
- dp[0][i], i ∈ {2, 4, 6, ······, p.length},意思是 s 为空字符串,当 p 为 "a*b*" 类似的模式时,dp[0][i] 为 true,否则 false。
- dp[i][0], i ∈ {1, 2, 3, ······, s.length},意思是 p 为空字符串,肯定不匹配,为 false。
public boolean isMatch(String s, String p) { boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]; dp[0][0] = true; for (int i = 2; i <= p.length(); i += 2) { if (p.charAt(i - 1) == ‘*‘) dp[0][i] = true; else break; } for (int i = 1; i <= s.length(); i++) { for (int j = 1; j <= p.length(); j++) { if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == ‘.‘) { // . or other character satified s[i] = p[j] dp[i][j] = dp[i - 1][j - 1]; } else if (j >= 2 && p.charAt(j - 1) == ‘*‘) { // *, size = 1, size > 1 if (p.charAt(j - 2) == ‘.‘ || s.charAt(i - 1) == p.charAt(j - 2)) { dp[i][j] = dp[i - 1][j - 2] || dp[i - 1][j]; } // *, size = 0 dp[i][j] = dp[i][j] || dp[i][j - 2]; } } } return dp[s.length()][p.length()]; }
动态规划,时间复杂度O(s.length * p.length),运行时间约为 32 ms。
总结
这个题目真的是难,动态规划的题目没有几个是简单的。曾经因为这个题目我放弃了刷 Leetcode,最近几天苦心研究,终于得出答案了。这可能是我最近最开心的一件事了。
动态规划最重要的一点是状态转移,只要能列出初始状态,写出状态转移方程,之后的问题就很好解决。
LeetCode - 10 - Regular Expression Matching
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。