Easy and concise C++ DP solution beats 97.43%


  • 0
    W
    class Solution {
    public:
        bool isMatch(string s, string p) {
            if (p.empty())
                return s.empty();
            bool T[p.size() + 1][ s.size() + 1];
            //T[i][j] == true means the last i characters of p match the last j characters of s.
            for(int i = 0 ; i <= p.size() ; i++)
                for(int j = 0 ; j <= s.size() ; j ++)
                    T[i][j] = false;
            T[0][0] = true;
            for(int i = 0; i <= p.size() - 1; i++){
                for(int j = 0; j <= s.size(); j++){
                	if(T[i][j] == false)
                		continue;
                	else if(i+1 <= p.size() && j+1 <= s.size() && (p[p.size() - 1 -i] == s[s.size() - 1 -j] || p[p.size() -1 - i] == '.'))
                	//if the next character of p equals the next character of s || the next character of p is '.'
                		T[i+1][j+1] = true;
                	else if(i+2 <= p.size() && p[p.size() - 1 -i] == '*' ){
                	//if the next character of p is '*'
                		T[i+2][j] = true;
                		int k = 1;
    	            	while(j+k <= s.size() && (s[s.size() - k -j] == p[p.size() - i -2] || p[p.size() - i -2] == '.')){
    	            	//if the next charater of s equals the character before '*' of p
    	            		T[i+2][j+k] = true;
    	            		k++;
    	            	}
                	}
                }
            } 
            return T[p.size()][s.size()];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.