JAVA-三种解法
正则表达式匹配
http://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c
剑指offer:52.正则表达式匹配
思路1 递归匹配
当模式中的第二个字符不是“*”时:
1、如果字符串第一个字符和模式中的第一个字符相匹配,那么字符串和模式都后移一个字符,然后匹配剩余的。
2、如果字符串第一个字符和模式中的第一个字符相不匹配,直接返回false。
而当模式中的第二个字符是“”时:
可以有3种匹配方式:
1、模式后移2字符,相当于x被忽略;匹配0位
2、字符串后移1字符,模式后移2字符,x相当于只匹配一个字符;
3、字符串后移1字符,模式不变,即继续匹配字符下一位,因为可以匹配多位;(包括匹配一位)
- 如果pattern[j] == '.'
- 如果str[i] == pattern[j]
以上两种情况都是i后移一位,然后j后移一位。
而当模式中的第二个字符是“*”时:
- 如果pattern[i] == '.' || str[i] == pattern[j],那么证明第一位相匹配,需要匹配0或多位 matchStr(str, i, pattern, j + 2) || matchStr(str, i + 1, pattern, j);;
- 反之,j后移两位。
代码
public class Solution { public boolean matchStr(char[] str, int i, char[] pattern, int j) { if (i == str.length && j == pattern.length) { // 字符串和模式串都为空 return true; } else if (j == pattern.length) { // 模式串为空 return false; } boolean next = (j + 1 < pattern.length && pattern[j + 1] == '*');// 模式串下一个字符是'*' //当模式中的第二个字符是“*”时: if (next) { if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) { //匹配零位 & 匹配多位 (即使这一位相同或者是.,也有可能只匹配零位,匹配一位的情况包含在递归里了) return matchStr(str, i, pattern, j + 2) || matchStr(str, i + 1, pattern, j); } else { //匹配零位(当这一位不相同而且还不是.的时候,只能忽略了) return matchStr(str, i, pattern, j + 2); } } //当模式中的第二个字符不是“*”时: else { //匹配一位 if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) { return matchStr(str, i + 1, pattern, j + 1); } else { //匹配这一位失败 return false; } } } public boolean match(char[] str, char[] pattern) { return matchStr(str, 0, pattern, 0); } }
思路2 动态规划
动态规划转移方程:
boolean dp[i][j]表示str的前i个和pattern的前j个能否匹配
第一个字符为str[0]
从pattern角度看过去
第j个字符,当前字符pattern[j-1]不是“*”:
如果 pattern[j-1] == '.' || str[i-1] == pattern[j-1]),dp[i][j] = dp[i-1][j-1]
否则,dp[i][j] =false;
第j个字符,当前字符pattern[j-1]是“*”:
比较pattern中前一字符pattern[j-2]与str[i-1]是否匹配
如果 pattern[j-2] == '.' || str[i-1] == pattern[j-2]),那么分两种情况
如果重复0次,dp[i][j] = dp[i][j-2]
如果重复1次或者多次,dp[i][j] = dp[i-1][j]
否则,
- 只有重复0次,dp[i][j] = dp[i][j-2]
动态规划初始条件:
str为空且pattern为空,为真: dp[0][0] = true
str不为空且pattern为空,为假: dp[1..sn][0] = false
pattern[j-1]=='*'时,dp[0,j]=dp[0,j-2];
否则dp[0,j]=false;
public class Solution { public boolean judge(char p,char s){ if(p=='.')return true; else return p==s; } public boolean match(char[] str, char[] pattern) { int pn=pattern.length; int sn=str.length; boolean[][] dp=new boolean[sn+1][pn+1]; //初始化 dp[0][0]=true; for(int j=1;j<=pn;j++){ if(pattern[j-1]=='*')dp[0][j]=dp[0][j-2]; } for(int i=1;i<=sn;i++){ for(int j=1;j<=pn;j++){ boolean now = (pattern[j-1] == '*');// 模式串当前字符是'*' if(!now){ if(judge(pattern[j-1],str[i-1])) dp[i][j]=dp[i-1][j-1]; } else{ if(judge(pattern[j-2],str[i-1])) dp[i][j]=dp[i][j-2]|dp[i-1][j]; else dp[i][j]=dp[i][j-2]; } } } return dp[sn][pn]; } }
思路3 和原正则表达式一致,使用库函数匹配
public class Solution { public boolean match(char[] str, char[] pattern) { return String.valueOf(str).matches(String.valueOf(pattern)); } }
import java.util.regex.*; public class Solution { public boolean match(char[] str, char[] pattern) { String pat = String.valueOf(pattern); //把.替换为正则表达式的\w 用以匹配一个任意字符 pat = pat.replaceAll("\\.", "\\\\w"); Pattern pattern1 = Pattern.compile(pat); Matcher matcher = pattern1.matcher(String.valueOf(str)); return matcher.matches(); } }
车轮滚滚 时间
import java.util.regex.*; [] : 字符集合 () : 分组 ? : 重复 0 ~ 1 次 + : 重复 1 ~ n 次 * : 重复 0 ~ n 次 . : 任意字符 \\. : 转义后的 . \\d : 数字 {n} :必须匹配n次 {n,}:必须匹配n次或以上 {n,m}:匹配次数在n到m之间,包括边界