首页 > 代码库 > 《剑指offer》 面试题53 ：正则表达式匹配 Java
《剑指offer》 面试题53 ：正则表达式匹配 Java
引言：这道题情况比较复杂，边界条件较多，为了便于以后复习，整理一下。另外，由于C语言和Java对于字符串的操作存在不一样的地方，代码也存在改动。
题目：请实现一个函数用来匹配包含‘.‘和‘*‘的正则表达式。模式中的字符‘.’表示任意一个字符，而‘*‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"及"ab*a"均不匹配。
分析：这道题的核心其实在于分析‘*‘,对于‘.‘来说，它和任意字符都匹配，可把其当做普通字符。对于‘*‘的分析，我们要进行分情况讨论，当所有的情况都搞清楚了以后，就可以写代码了。
在每轮匹配中，Patttern第二个字符是‘*‘时：
- 第一个字符不匹配（‘.‘与任意字符视作匹配），那么‘*‘只能代表匹配0次，比如‘ba‘与‘a*ba‘，字符串不变，模式向后移动两个字符，然后匹配剩余字符串和模式
- 第一个字符匹配，那么‘*‘可能代表匹配0次，1次，多次，比如‘aaa‘与‘a*aaa‘、‘aba‘与‘a*ba‘、‘aaaba‘与‘a*ba‘。匹配0次时，字符串不变，模式向后移动两个字符，然后匹配剩余字符串和模式；匹配1次时，字符串往后移动一个字符，模式向后移动2个字符；匹配多次时，字符串往后移动一个字符，模式不变；
而当Patttern第二个字符不是‘*‘时，情况就简单多了：
- 如果字符串的第一个字符和模式中的第一个字符匹配，那么在字符串和模式上都向后移动一个字符，然后匹配剩余字符串和模式。
- 如果字符串的第一个字符和模式中的第一个字符不匹配，那么直接返回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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。