题解 | #正则表达式匹配#
正则表达式匹配
https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4
import java.util.*; public class Solution { public boolean match (String str, String pattern) { int s = str.length() + 1; int p = pattern.length() + 1; str = " " + str; pattern = " " + pattern; boolean[][] f = new boolean[s][p]; f[0][0] = true; for (int i = 0; i < s; i++) { for (int j = 1; j < p; j++) { // pattern的j位置不为* if (pattern.charAt(j) != '*') { f[i][j] = i >= 1 && f[i - 1][j - 1] && (str.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '.'); } else { //pattern的j位置为*时,可能匹配0个或多个 f[i][j] = (j >= 2 && f[i][j - 2]) || (i >= 1 && f[i - 1][j] && (str.charAt(i) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')); } } } return f[s - 1][p - 1]; } }