【LeetCode】10. Regular Expression Matching，leetcodematching

【LeetCode】10. Regular Expression Matching，leetcodematching

題目：

　　Implement regular expression matching with support for '.' and '*'.

　　'.' Matches any single character.
　　'*' Matches zero or more of the preceding element.

思路：'.' 代表任意單字符，'*' 可以代表將前面的字符去掉，也可以代表是對前面字符(包括'.')的重復（數目無限）。例子：

　　　　aa  a　　　　 //不匹配，很明顯

　　　　aa  aa　　　  //匹配

　　　　aaa  aa 　　  //不匹配

　　　　aa  a*　　　 //匹配，*重復a

　　　　aa  .*　　　 //匹配，.代表a，*重復a

　　　　ab  .*　　　 //匹配，.代表a，*重復.本身（不是.代表的a），代表b          也就是說.*可以是..   ...   .....等等，可匹配任意字符串

　　　　aab  c*a*b  //匹配，第一個*將c字符去掉，aab與a*b很明顯匹配

public class Solution {
    public boolean isMatch(String s, String p) {
        /*
        if(p.length()==0){
            return s.length()==0;
        }
        
        if(p.length()==1){
            return s.length()==1&&(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.');
        }
        
        if(p.charAt(1)=='*'){
            if(isMatch(s,p.substring(2))){
                return true;
            }
            return s.length()>0&&(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')&&isMatch(s.substring(1),p);
        }else{
            return s.length()>0&&(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')&&isMatch(s.substring(1),p.substring(1));
        }
        */
        return isMatch(s, 0, p, 0);
    }
    private boolean isMatch(String s, int i, String p, int j) {
		int ls = s.length();
		int lp = p.length();
		if (j == lp) {
			return i == ls;
		}
		// case 1: when the second char of p is not '*'
		if ((j < lp - 1 && p.charAt(j + 1) != '*') || j == lp - 1) {
			return (i < ls && s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') && isMatch(s, i + 1, p, j + 1);
		}
		// case 2: when the second char of p is '*', complex case.
		while ((i < ls && s.charAt(i) == p.charAt(j)) || (p.charAt(j) == '.' && i < ls)) {
			if (isMatch(s, i, p, j + 2))
				return true;
			i++;
		}
		return isMatch(s, i, p, j + 2);
	}
}