leetcode 10 번 문제 (자바 해법)

Given an input string ( s ) and a pattern ( p ), 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).
Note:

s  could be empty and contains only lowercase letters  a-z .

p  could be empty and contains only lowercase letters  a-z , and characters like  .  or  * .

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

 
인터넷 블 로 거 c 언어의 사고방식 을 참고 하여 뒤에서 앞으로 일치 하 므 로 경 계 를 넘 는 상황 을 고려 할 필요 가 없다.(역 추적 법)

public static boolean isMatch(String s, String p) {
    return myMacth(s,s.length()-1,p,p.length()-1);
}
private static boolean myMacth(String s,int i,String p,int j){
    System.out.println(i+"  "+j);
    if(j==-1)
        if(i==-1)
            return true;
    else return false;
    if(p.charAt(j)=='*'){//   *，     *    s     ，      ，         ，     。
        if(i >= 0 &&(p.charAt(j-1)=='.'||p.charAt(j-1)==s.charAt(i))){
            if(myMacth(s,i-1,p,j))
                return true;
        }
        return myMacth(s,i,p,j-2);
    }
    if(i==-1&&j>=0) return false;//       ，s        ，  p     。
    if(p.charAt(j)=='.'||p.charAt(j)==s.charAt(i))
        return myMacth(s,i-1,p,j-1);
    return false;
}