C++ standard DP without tricks, not so fast but accepted


  • 0
    S
    Define a function L(j, i) to represent if there is a match between  s[j], s[j+1] ... s[m + 1] and p[i], p[i+1], ... ,p[n + 1]
    Boundary:
    L(m + 1, n + 1) = 1   (empty matches empty)
    L(m + 1, i) = 1 (if i start from n , and characters between p[i]...p[n] are all '*')
    Recurrence:
                   {for k = j to m + 1, if there exist a L(k, i + 1)  == true then true, otherwise false}  (if p[i] == '*')   
    L(j, i) =      L(j + 1, i + 1) (if p[i] == '?')
                   {L(j + 1, i + 1) if s[j] == p[i], false otherwise} (if p[i] == other characters) 
    

    //Code:

    class Solution {
        public:
        
            bool isMatch(string s, string p) {
                int m = s.length(), n = p.length();
                if(n == 0 && m != 0) return false;
                vector<char> dp_row(s.length() + 1, 0);
                vector<vector<char>> dp_arr(p.length() + 1, dp_row);
                
                dp_arr[n][m] = 1;
                for(int i = n-1; i >= 0; i--){
                    if(p[i] == '*') dp_arr[i][m] = 1;
                    else break;
                }
                for(int i = n - 1; i >= 0; i--){
                    for(int j = m - 1; j >= 0; j--){
                        if(p[i] == '*'){
                            bool found_valid = false;
                            for(int k = j; k <= m; k++){
                                if(dp_arr[i+1][k] == 1){
                                    found_valid = true;
                                    break;
                                }
                            }
                            if(found_valid) dp_arr[i][j] = 1;
                            else dp_arr[i][j] = 0;
                        } else if(p[i] == '?'){
                            dp_arr[i][j] = dp_arr[i+1][j+1];
                        } else {
                            if(p[i] == s[j]) dp_arr[i][j] = dp_arr[i+1][j+1];
                            else dp_arr[i][j] = 0;
                        }
                    }
                }
                if(dp_arr[0][0]== 1) return true;
                else return false;
            }
            
        
        };

  • 0
    C

    Thanks to your idea,I came up with the following code.But the result is always TLE and I still cannot find why it happens.Could you please help me find what's wrong with my code?

    bool isMatch(string s, string p)
    {
    	int m = s.length(), n = p.length();
    	if(n==0&&m!=0){return false;}
    	vector<vector<bool>>dp(m+1, vector<bool>(n+1,false));
    	dp[0][0] = true;
    	for (int i = 1; i <= m; i++)
    	{
    		dp[i][0] = false;
    	}
    	for (int j = 1; j <= n;j++)
    	{
    		if (p[j - 1] == '*') { dp[0][j] = true; }
    		else { break; }
    	}
    	for (int i = 1; i <= m; i++)
    	{
    		for (int j = 1; j <= n; j++)
    		{
    			if (p[j - 1] == '*') {
    				dp[i][j] = false;
    				for (int k = 0; k <= i; k++) {
    					if (dp[k][j - 1] ) { dp[i][j] = true; break; }
    				}
    				//if (dp[i - 1][j]) { dp[i][j] = true; }
    			}
    			else if (p[j - 1] == '?') {
    				dp[i][j] = dp[i - 1][j - 1];
    			}
    			else {
    				if (s[i-1] == p[j-1]) { dp[i][j] = dp[i - 1][j - 1]; }
    				else { dp[i][j] = false; }
    			}
    		}
    	}
    	return dp[m][n];
    }

Log in to reply
 

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