正则表达式匹配

描述

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

数据范围：字符串长度 。 要求：空间复杂度 ，时间复杂度

提示：如果输入空字符串，则返回True

思路

这里我尝试的暴力解法，即通过一个个比较，如果全部都对，则返回true。

通过表达式为逐字判断，特别是处理"." 和""的技巧，这里因为涉及到的前面字符可以很多个，不如从都从最后一个字符判断起。

当然，为了简化思路，把几个特例单独拿出来判断，如：“.*”. '.'等。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
      
      //我的目的很简单，只希望小白也能快速看懂
        
        char [] pat=pattern.toCharArray(); //转化为数组，便于处理，下同
        char [] strc=str.toCharArray();
       
        int len2=strc.length;
        int len1=pat.length;       
        int i=len2-1;//i为字符串比较下标，j为表达式下标，若都等于-1则成功
        int j=len1-1;
        
        if(len1==2){    
          //排掉一个特例；".*"
            if(pat[0]=='.' && pat[1]=='*'){
                return true;
            }
        }
        if(i>=0 && j<0){//排掉表达式为空的
            return false;
        }
        if(len1==0 && len2==0){//都是空的
            return true;
        }
        
        while(i>=0){
          
          //因为i，j下标移动的速度不一样，只以i为准
            
            if((strc[i]==pat[j] || pat[j]=='.') && (i>=0)){
                i--;
                j--;
                if(i==-1  || j==-1){//这里提前判断
                    break;
                }
                
            }else if(pat[j]=='*'){ //比较*
                while(pat[j-1] ==strc[i]){                    
                    if(i>0){
                        i--;
                    }else{
                        break; //主要前缀可能全部是符合 字符*
                    }                  
                }
                j=j-2;
                if(j<0){
                    return true; //这里j移动了2个字符，要判断是否越界
                }
            }else{
                return false; //只要有一项不同，便返回fasle
            }
        }        
        if(i==-1 && j ==-1){            
           return true;  //这里都比较完了，则返回true
        }
        else if(i==-1 ){  //这里一个特例 但字符串只有一个，表达式为 字符* ，时，
            if(pat.length==2 ){
                if(pat[1]=='*'){
                    return true;
                }
            }
            return false;
        }
        else{
            return false;//这里我反正为了保险，写的一个判断
        }
    }
}

最后

其实，最后测试的时候，自己发现一个用例 "aaaa","a.*" 这种的，按理说应该符合的，但我这个返回false，但测通评测oj ,所以我的这个还要优化