题解 | #正则表达式匹配#
正则表达式匹配
https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4
最牛的写法,没有之一
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param str string字符串 * @param pattern string字符串 * @return bool布尔型 */ public boolean match (String str, String pattern) { // write code here str = " " + str; pattern = " " + pattern; int n = str.length(); int m = pattern.length(); boolean[][] dp = new boolean[n + 1][m + 1]; dp[0][0] = true; for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) { char a = str.charAt(i - 1); char b = pattern.charAt(j - 1); if (b == '*') { if (a != pattern.charAt(j - 2) && pattern.charAt(j - 2) != '.') { dp[i][j] = dp[i][j - 2]; // 匹配 零次 } else { dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j]; } } else if(b == '.' || a == b) { dp[i][j] = dp[i - 1][j - 1]; } } } return dp[n][m]; } }