正则表达式匹配

问题描述

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

思路分析

先考虑模式串中有’‘的情况，因为可以匹配0个或多个，所以如果模式串的下一个字符是的时候就有三种情况
1.匹配0个主串的字符，比如主串是abc，模式串是b，那么下一步匹配的策略是主串保持不变，模式串跳到下两个字符重新比较，
2.匹配1个字符，比如主串是abc，模式串是a，下一步比较策略是主串跳到下一个字符，模式串移动两个字符
3.匹配多个字符，比如主串aac，模式串是acb，因为只匹配aa两个字符，下一步策略是主串移动一个字符，模式串移动两个字符，如果当前字符与主串字符不能匹配，则主串不变，模式串移动两个位置
如果当前字符是’.’，直接按逐个字符进行比较

码上有戏

public boolean match(char[] str,char[] pattern){
    if(str==null||pattern==null)
      return false;
    return matchRegCore(str,0,str.length,pattern,0,pattern.length);
  }
  
  private boolean matchRegCore(char[] str,int i,int length1,char[] pattern,int j,int length2){
    if(i==length1&&j==length2){
      if(j==length2||pattern[j]=='*')
        return true;
      else
        return false;
    }
    if(i!=length1&&j==length2)
      return false;
    if(j+1<length2&&pattern[j+1]=='*'){
      if(i<length1&&(pattern[j]==str[i]||pattern[j]=='.')){
        return matchRegCore(str,i+1,length1,pattern,j,length2)||
            matchRegCore(str,i+1,length1,pattern,j+2,length2)||
            matchRegCore(str,i,length1,pattern,j+2,length2);
      }else{
        return matchRegCore(str,i,length1,pattern,j+2,length2);
      }
    }
    if(i<length1&&(str[i]==pattern[j]||pattern[j]=='.')){
      return matchRegCore(str,i+1,length1,pattern,j+1,length2);
    }
    return false;
  }