Leetcode \ # 10 정규 표현 식 일치 문제 풀이 소절

원제
원제
Implement regular expression matching with support for ‘.’ and ‘*’.
‘.’ Matches any single character. ‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be: bool isMatch(const char *s, const char *p)
Some examples: isMatch(“aa”,”a”) → false isMatch(“aa”,”aa”) → true isMatch(“aaa”,”aa”) → false isMatch(“aa”, “a*”) → true isMatch(“aa”, “.*”) → true isMatch(“ab”, “.*”) → true isMatch(“aab”, “c*a*b”) → true
2 문제 이해
정규 표현 식 을 지정 하고 문자열 과 일치 하 는 지 여 부 를 판단 하 는 것 은 간단 합 니 다.
문제 풀이 방식: 재 귀적 으로 만 났 습 니 다. * 가 없 는 것 과 직접 만 났 습 니 다 *. 매번 건 너 뛰 고 일치 하 는 두 가지 로 나 누 었 습 니 다.
상세 하 게 제 코드 설명 을 보 세 요.
3 AC 분해

/** * *        ，    ，           ： * 1、       *  ， *         ，1  * * a、*        （.     ),          ，            ，      *  ，     b * b、  *，   ，       * 2、    * * a、         ，         * b、  gameover * 3、          ，      ，  true * 4、            ，       ，  ： * a、  pattern           *   ，       *   ，        * b、      ，  p     ，         ，       * */

public class Solution {
    char[] subject;
    char[] pattern;
    int slen,plen;
    public boolean check(int si,int pi){
        if(si==slen && pi==plen) //   3
            return true;
        if(si<slen && pi<plen){
            if(pi<plen-1 && pattern[pi+1]=='*'){
                boolean same=false;
                if(pattern[pi]=='.' || pattern[pi]==subject[si])
                    same=true;
                boolean flag=false;
                if(same)
                    flag=check(si+1,pi); //   1.a
                if(flag==false)
                    flag=check(si,pi+2); //   1.b
                return flag;
            } else{
                if(pattern[pi]=='.' || pattern[pi]==subject[si])
                    return check(si+1,pi+1);//  2.a
                return false; //  2.b
            }
        } 
        else{
            while (pi<plen-1 && pattern[pi+1]=='*'){ //  4   
                pi+=2;
            }
            if(si==slen && pi==plen) //  4.a   4.2b pattern    
                return true;
            return false;//  4.a   4.2b pattern       
        }

    }
    public boolean isMatch(String s, String p) {
        slen=s.length();
        plen=p.length();
        subject=s.toCharArray();
        pattern=p.toCharArray();
        return check(0,0);
    }
}