【题目】请实现一个函数用来匹配包括’.’和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”aba”均不匹配
package com.exe6.offer;
/**
* 【题目】请实现一个函数用来匹配包括’.’和’*‘的正则表达式。模式中的字符’.’表示任意一个字符，
* 而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。
* 例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”aba”均不匹配
* @author WGS
*
*/
public class MatchRegString { public boolean match(char[] str,char[] pattern){
if(str==null ||pattern==null)
return false;
return matchCore(str,0,str.length,pattern,0,pattern.length);
} public boolean matchCore(char[] str, int i, int length1, char[] pattern, int j, int length2) {
if(i==length1 && j==length2){
return true;
/*if(j==length2 || pattern[j]=='*'){
return true;
}else{
return false;
}*/
}
if(i!=length1 && j==length2){
return false;
}
//3 当pattern中下一个字符有'*'时
if(j+1<length2 && pattern[j+1]=='*'){
//① a A a与a A * a 即*前值与str中要比较的值相同
// a A a与a . * a
if(str[i]==pattern[j]){
//后移两位
return matchCore(str,i+1,length1,pattern,j+2,length2)
//在原状态
|| matchCore(str,i+1,length1,pattern,j,length2)
//忽略
|| matchCore(str,i+1,length1,pattern,j+2,length2);
}
//②a A a与a B * a 即*前值与str中要比较的值不同 pattern就忽略*前的值，后移两位继续比较,str 值不变
else{
return matchCore(str,i,length1,pattern,j+2,length2);
}
} //1 2 当前字符匹配或者匹配'.' 两者均右移一位继续比较；
if(i<length1 && (str[i]==pattern[j] || pattern[j]=='.')){
return matchCore(str,i+1,length1,pattern,j+1,length2);
}
return false;
} public static void main(String[] args) {
char[] str=new char[]{'a', 'a', 'a'};
char[] pattern=new char[]{'a', 'b','*','a', 'c','*','a'};
MatchRegString m=new MatchRegString();
boolean b=m.match(str, pattern);
System.out.println(b); } }