首页 > 代码库 > 《剑指offer》 面试题53 :正则表达式匹配 Java

《剑指offer》 面试题53 :正则表达式匹配 Java

引言:这道题情况比较复杂,边界条件较多,为了便于以后复习,整理一下。另外,由于C语言和Java对于字符串的操作存在不一样的地方,代码也存在改动。

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

分析:这道题的核心其实在于分析‘*‘,对于‘.‘来说,它和任意字符都匹配,可把其当做普通字符。对于‘*‘的分析,我们要进行分情况讨论,当所有的情况都搞清楚了以后,就可以写代码了。

在每轮匹配中,Patttern第二个字符是‘*‘时:

  1. 第一个字符不匹配(‘.‘与任意字符视作匹配),那么‘*‘只能代表匹配0次,比如‘ba‘与‘a*ba‘,字符串不变,模式向后移动两个字符,然后匹配剩余字符串和模式
  2. 第一个字符匹配,那么‘*‘可能代表匹配0次,1次,多次,比如‘aaa‘与‘a*aaa‘、‘aba‘与‘a*ba‘、‘aaaba‘与‘a*ba‘。匹配0次时,字符串不变,模式向后移动两个字符,然后匹配剩余字符串和模式;匹配1次时,字符串往后移动一个字符,模式向后移动2个字符;匹配多次时,字符串往后移动一个字符,模式不变;

而当Patttern第二个字符不是‘*‘时,情况就简单多了

  1. 如果字符串的第一个字符和模式中的第一个字符匹配,那么在字符串和模式上都向后移动一个字符,然后匹配剩余字符串和模式。
  2. 如果字符串的第一个字符和模式中的第一个字符不匹配,那么直接返回false。

好,现在思路已经清楚了,可以看代码了:

 

 1 package test;
 2 import java.util.Scanner;
 3 
 4 public class Question_53 {
 5     public static boolean match(String input,String pattern){
 6         if(input==null||pattern==null) return false;
 7         return matchCore(input,0,pattern,0);
 8     }
 9     private static boolean matchCore(String input,int i,String pattern,int p){
10         if((input.length()==i)&&(pattern.length()==p)){
11             //出口1,input和pattern都到了字符串末尾
12             return true;
13         }
14         if((i!=input.length())&&(pattern.length()==p)){
15             //出口2,字符串input没有到末尾,pattern到了末尾
16             return false;
17         }
18         if((input.length()==i)&&(pattern.length()!=p)){
19             //出口3,字符串input到末尾,pattern还没有到末尾
20             return false; 
21         }
22         
23         if((p+1<pattern.length())&&(pattern.charAt(p+1)==‘*‘)){//pattern第二个字符为*
24             if((input.charAt(i)==pattern.charAt(p))||(pattern.charAt(p)==‘.‘)){
25                 //首字母相匹配
26                 return matchCore(input,i+1,pattern,p+2) //*表示出现1次
27                      ||matchCore(input,i+1,pattern,p)    //*表示出现多次
28                      ||matchCore(input,i,pattern,p+2);   //*表示出现0次 , a ...  p* ...
29             }else{
30                 //首字母不匹配
31                 return matchCore(input,i,pattern,p+2);
32             }
33         } //end pattern.charAt(p+1)==‘*‘
34         
35         if((input.charAt(i)==pattern.charAt(p))||(pattern.charAt(p)==‘.‘)){
36             //pattern第二个字母不是*,且首字母匹配
37             return matchCore(input,i+1,pattern,p+1);
38         }
39         return false;  //其余情况全部不匹配
40     }
41 
42     public static void main(String[] args) {
43         // TODO Auto-generated method stub
44          Scanner scanner = new Scanner(System.in);                       //扫描键盘输入  
45          System.out.println(" 请输入第一个字符串:");  
46          String str1 = scanner.nextLine();             
47          System.out.println(" 请输入第二个字符串:");  
48          String str2 = scanner.nextLine();
49          scanner.close();
50          
51          System.out.print("匹配的结果为:");  
52          System.out.println(match(str1, str2));  
53     }
54 
55 }

 

注意边界条件,当模式和字符串都只剩一个字符时, pattern.charAt(p+1)==‘*‘ 会访存越界,所以需要加额外的限制条件 p+1<pattern.length() ,这样这个条件不能满足就会进入下一个if判断语句,直接判断两个字符是不是相等,最后进入出口1,返回true。字符串和模式任意一个先结束都视作不匹配,返回false,这就是出口2和出口3. 

 

《剑指offer》 面试题53 :正则表达式匹配 Java