正则表达式匹配
请实现一个函数用来匹配包括’.‘和’*'的正则表达式。
模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。
样例 输入： s="aa" p="a*" 输出:true
递归
时间复杂度O(n^2)
class Solution { public boolean isMatch(String s, String p) { if(s == null || p== null || (s.length()!=0 && p.length()==0)) { return false; } char[] str = s.toCharArray(); char[] pat = p.toCharArray(); return matchCore(str,0,pat,0); } private boolean matchCore(char[] str, int indexOfStr, char[] pattern, int indexOfPattern) { if (indexOfStr == str.length && indexOfPattern == pattern.length){ return true;} if (indexOfStr < str.length && indexOfPattern == pattern.length) { return false; } if (indexOfPattern + 1 < pattern.length && pattern[indexOfPattern + 1] == '*') { if ((indexOfStr < str.length && pattern[indexOfPattern] == '.') || (indexOfStr < str.length && pattern[indexOfPattern] == str[indexOfStr])) { return matchCore(str, indexOfStr, pattern, indexOfPattern + 2) || matchCore(str, indexOfStr + 1, pattern, indexOfPattern) || matchCore(str, indexOfStr + 1, pattern, indexOfPattern + 2); } else { return matchCore(str, indexOfStr, pattern, indexOfPattern + 2); } } if (indexOfStr < str.length && (pattern[indexOfPattern] == str[indexOfStr] || (pattern[indexOfPattern] == '.'))){ return matchCore(str, indexOfStr + 1, pattern, indexOfPattern + 1); } return false; } }
DP
时间复杂度O(nm)
class Solution { static boolean[][] dp; static int n,m; public static boolean isMatch(String s, String p){ char[] ss = s.toCharArray(); char[] ps = p.toCharArray(); dp = new boolean[ss.length + 1][ps.length + 1]; n = ss.length; m = ps.length; dp[n][m] = true; return dp(0,0,ss,ps); } private static boolean dp(int i, int j, char[] ss, char[] ps){ if (dp[i][j]){ return dp[i][j]; } // 模式串匹配完成，判断是否匹配完字符串 if (j == m){ return dp[i][j] = i == n; } // 出现两个串字符相同或者模式串为'.'时则为true boolean firstMatch = i < n && (ss[i] == ps[j] || ps[j] == '.'); boolean ans; if (j + 1 < m && ps[j + 1] == '*'){ // j + 2意味着 *号和之前的一个元素没有被匹配到则跳过 ans = dp(i,j + 2, ss, ps) || firstMatch && dp(i + 1, j, ss, ps); }else { ans = firstMatch && dp(i + 1, j + 1, ss, ps); } return dp[i][j] = ans; } }
