请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配；
这是剑指offer的一道原题，为了解决该问题，可以将字符串和模式串的匹配情况，分为以下三种情况；
-
模式为单个'.'或者单个普通字母时： 直接判断。
-
模式为普通字母和'*'的组合时，就是说普通字母后面跟着一个匹配符'*'，例如 'A','*'： 从这一位到与这一位的字符相等的位的下一位，逐次递归。
-
模式为'.'和'*'的组合时，就是说'.'后面跟着一个匹配符'*'，也就是'.','*'这种情况： 从这一位到最后一位，逐次递归。
1 /**
2 * Created by hardaway on 2018/7/25.
3 */
4 public class Code16 {
5
6 public boolean match(char[] str, char[] pattern){
7 if(str.length==0){
8 return check(0,pattern);
9 }
10 return match(str,pattern,0,0);
11 }
12 public boolean match(char[] str, char[] pattern, int is, int js){
13 int j = js;
14 int i = is;
15 for( ; i<str.length&&j<pattern.length; ){
16 // 模式为 .* 时：
17 if((j<pattern.length-1)&&(pattern[j+1]=='*')){
18 if(pattern[j]=='.'){
19 if(j+2==pattern.length)
20 return true;
21 boolean flag = false;
22 for(int ii = i; ii<str.length; ii++){
23 if(str[ii]==pattern[j+2]){
24 flag = match(str,pattern,ii,j+2);
25 if(flag) break;
26 }
27 }
28 return flag;
29 // 模式为 普通字母* 时： eg. A*
30 }else{
31 if(str[i] == pattern[j]){
32 int str_len = getLength(i,str,str[i]);
33 if(j+2==pattern.length){
34 if(i+str_len==str.length)
35 return true;
36 }
37 boolean flag = false;
38 int right = i+str_len;
39 for(int ii = i; ii<str.length&&ii<=right; ii++){
40 flag = match(str,pattern,ii,j+2);
41 if(flag) break;
42 }
43 return flag;
44 }else {
45 i = i;
46 j = j + 2;
47 }
48 }
49 // 模式为单个 . 或者单个普通字母时：
50 }else{
51 if(str[i]==pattern[j]||pattern[j]=='.'){
52 i++; j++;
53 }else{
54 return false;
55 }
56 }
57 }
58 if(i==str.length)
59 return check(j,pattern);
60 return false;
61 }
62 public boolean check(int sta , char[] arr){
63 boolean flag = false;
64 if ((arr.length-sta)%2==0){
65 int i = sta+1;
66 while (i<arr.length&&arr[i]=='*'){
67 i=i+2;
68 }
69 if(i==arr.length+1)
70 flag = true;
71 }
72 return flag;
73 }
74 public int getLength(int i, char[] arr,char obj){
75 int len = 0;
76 while(i<arr.length&&arr[i]==obj){
77 i++;
78 len++;
79 }
80 return len;
81 }
82 public static void main(String[] args) {
83 Code16 c =new Code16();
84 char[] str = {};//{'a','b','c','d','a','b','b','b','b','b','b','d'};
85 char[] pattern ={'.','*'};// {'a','b','c','.','a','.','*','b','d'};
86 System.out.println(c.match(str,pattern));
87 }
88 }
