Topic describes

// a regular // expression that supports both '.' and '*'. // '.' matches any single character. // '*' matches zero or more of the preceding elements.Copy the code

Answer key

// This is the same as offer 19. / / class recursive method Solution {public Boolean isMatch (String s, String p) {if (s = = null | | p = = null) return false. int si = 0; int pi = 0; return isMatch(s, p, 0, 0); } private boolean isMatch(String s, String p, int si, int pi) { if (pi == p.length() && si == s.length()) return true; if (si < s.length() && pi == p.length()) return false; if (pi + 1 < p.length() && p.charAt(pi + 1) == '*') { if ((si < s.length() && s.charAt(si) == p.charAt(pi)) || (si < s.length() && p.charAt(pi) == '.')) { return isMatch(s, p, si, pi + 2) || isMatch(s, p, si + 1, pi + 2) || isMatch(s, p, si + 1, pi); } else { return isMatch(s, p, si, pi + 2); } } else { if ((si < s.length() && s.charAt(si) == p.charAt(pi)) || (si < s.length() && p.charAt(pi) == '.')) return isMatch(s, p, si + 1, pi + 1); } return false; }} // Dynamic programming // optimal solution // execution time: 4 ms, beat 80.70% of users in all Java commits // memory consumption: Class Solution {public Boolean isMatch(String s, String p) { if (s == null || p == null) return false; char[] str = s.toCharArray(); char[] pattern = p.toCharArray(); int slen = str.length; int plen = pattern.length; boolean[][] dp = new boolean[slen + 1][plen + 1]; dp[0][0] = true; for (int i = 1; i <= plen; i++) { if (pattern[i - 1] == '*') dp[0][i] = dp[0][i - 2]; } for (int i = 1; i <= slen; i++) { for (int j = 1; j <= plen; j++) { if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.') { dp[i][j] = dp[i - 1][j - 1]; } else if (pattern[j - 1] == '*') { if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.') { dp[i][j] |= dp[i][j - 1]; dp[i][j] |= dp[i - 1][j]; dp[i][j] |= dp[i][j - 2]; } else { dp[i][j] = dp[i][j - 2]; } } } } return dp[slen][plen]; }}Copy the code