Accelerating DP in C++, without explanation


  • 1
    class Solution {
    public:
        bool isMatch(string s, string p) {
        int sLen = s.length(), pLen = p.length();
        bool **match = new bool*[sLen+1];
        for(int i = 0; i <= sLen; i++) match[i] = new bool[pLen+1]();
        match[0][0] = true;
        for(int i = 1; i <= pLen; ++i)
            if(p[i-1] == '*') match[0][i] = true; else break;
        for(int i = 1; i <= sLen; ++i){
            for(int j = 1; j <= pLen; ++j) {
                if(p[j-1] == '*') match[i][j] = match[i-1][j] || match[i][j-1];
                else match[i][j] = (s[i-1]==p[j-1] || p[j-1]=='?') && match[i-1][j-1];
            }
        }
        bool ret = match[sLen][pLen]; 
        for(int i = 0; i <= sLen; ++i) delete [] match[i];
        delete [] match;
        return ret;
    }
    };
    

    The normal DP solution above will cost 500ms. But if we eliminate some corner cases - counting the * as follows, it will be accelerated to 60ms.

            int count = 0;
    	for(int i = 0; i < pLen; i++) if(p[i] == '*') count++;
    	if((count==0 && pLen!=sLen) || (pLen-count>sLen)) return false;
    

    More optimised solutions using DP costing 28ms are :

    bool isMatch(string s, string p) {
    	int sLen = s.length(), pLen = p.length();
    	int match[sLen+1]{0};
    	match[0] = 1;
    	for(int i = 0; i < pLen; ++i) {
    		if(p[i] == '*') {
    			for(int j = 1; j <= sLen; ++j)
    				match[j] = match[j-1] || match[j];
    		}
    		else {
    			int t0, t1 = match[0];
    			for(int j = 1; j <= sLen; ++j) {
    			    t0 = match[j];
    			    match[j] = t1 && (p[i]=='?' || p[i]==s[j-1]);
    			    t1 = t0;
    			}
    			match[0] = 0;
    		}
    	}
    	bool ret = match[sLen];
            delete [] match;
    	return ret;
    }
    

    More terse version:

    bool isMatch(string s, string p) {
    	int sLen = s.length(), pLen = p.length();
    	int count = 0;
    	for(int i = 0; i < pLen; i++) if(p[i] == '*') count++;
    	if((count==0 && pLen!=sLen) || (pLen-count>sLen)) return false;
    	int *match = new int[sLen+1]();
    	match[0] = 1;
    	for(int i = 0; i < pLen; ++i) {
    		if(p[i] == '*') {
    			for(int j = 1; j <= sLen; ++j) match[j] = match[j-1] || match[j];
    		}
    		else {
    			for(int i = sLen; j > 0; --j)
    				match[j] = match[j-1] && (p[i]=='?' || p[i]==s[j-1]);
    			match[0] = 0;
    		}
    	}
        bool ret = match[sLen];
        delete [] match;
        return ret;
    }
    

    The legendary iterative solution, not a DP but efficient.

    bool isMatch(string s, string p) {
        int sIndex=0, pIndex=0;
        int sAIndex=-1, pAIndex=-1;
        int sLen=s.length(), pLen=p.length();
        while(sIndex < sLen) {
            if(s[sIndex]==p[pIndex] || p[pIndex]=='?') { sIndex++, pIndex++; continue;  }
            if(p[pIndex] == '*') { pAIndex = pIndex++; sAIndex = sIndex; continue;  }
            if(pAIndex > -1) { pIndex = pAIndex+1; sIndex = ++sAIndex; continue;  }
            return false;
        }
        while(p[pIndex] == '*') pIndex++;
        return pIndex==pLen;
    }

  • 0
    S

    @LHearen Do you have any idea, why my submissions were not there as usual, not found in the server Weird!!!


  • 1

    @Salkexy2 Sorry about that, the server sometimes crashed for the high frequent retrieving and visiting. Sorry about that. @1337c0d3r I think we will do better to further avoid this case.


Log in to reply
 

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