LeetCode10. Regular Expression Matching은 좀 어려워요.

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
class Solution {
public:
    bool isMatch(string s, string p) {
    	int sL = s.size() ;
    	int pL = p.size() ;
    	bool **dp = new bool*[sL+1];
    	for (int i = 0; i < sL+1;i++) {
    		dp[i] = new bool[pL+1];
    	}
    	for (int i = 0; i < sL+1; i++) {
    		for (int j = 0; j < pL; j++) {
    			dp[i][j] = false;
    		}
    	}
    	dp[0][0] = true;
    
    	for (int i = 0; i <= sL; i++) {
    		for (int j = 1; j <= pL; j++) {
    			char c = p[j - 1];
    			if (c != '*') {
    				dp[i][j] = i > 0 && dp[i - 1][j - 1] && (c == '.' || c == s[i - 1]);
    			}
    			else {
    				dp[i][j] = (dp[i][j - 2]) || 
    					(i > 0 && dp[i-1][j] && (p[j - 2] == '.' || p[j-2] == s[i-1]));
    			}
    		}
    	}
    	return dp[sL][pL];
    }
};

좋은 웹페이지 즐겨찾기