模式匹配算法-Java实现

2018/07/25 17:29
阅读数 19

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配;

这是剑指offer的一道原题,为了解决该问题,可以将字符串和模式串的匹配情况,分为以下三种情况;

  1. 模式为单个'.'或者单个普通字母时: 直接判断。

  2. 模式为普通字母和'*'的组合时,就是说普通字母后面跟着一个匹配符'*',例如 'A','*': 从这一位到与这一位的字符相等的位的下一位,逐次递归。

  3. 模式为'.'和'*'的组合时,就是说'.'后面跟着一个匹配符'*',也就是'.','*'这种情况: 从这一位到最后一位,逐次递归。

 

 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 }

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部