I got Memory Limit Exceeded


  • 7
    V

    Following is my code, I don't know what I got the Memory Limit Exceeded error.

    public boolean isMatch(String s, String p) {
    	int lenS = s.length();
    	int lenP = p.length();
    
    	boolean[][] dp = new boolean[lenS + 1][lenP + 1];
    	dp[0][0] = true;
    	for (int i = 1; i <= lenS; i++) {
    		for (int j = 1; j <= lenP; j++) {
    			if (p.charAt(j - 1) == '*') {
    				dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1];
    				if (j == lenP && dp[i][j]) {
    					return true;
    				}
    			} else if (s.charAt(i - 1) == p.charAt(j - 1)
    					|| p.charAt(j - 1) == '?') {
    				dp[i][j] = dp[i - 1][j - 1];
    			}
    		}
    	}
    	return dp[lenS][lenP];
    }

  • 0
    H

    Here my c++ code. We have very similar idea and my code gets MLE too. Anyone can help?

    class Solution {
     public:
    	 bool isMatch(const char *s, const char *p) {
    	     int lens = strlen(s), lenp = strlen(p);
    	     
    	     if (lenp==0 && lens!=0) return false;
    	     else if (lens == 0 && lenp != 0) {
    	         while (lenp>=0) {
    	             if (p[--lenp]!='*') return false;
    	         }
    	         return true;
    	     }
    	     
    	     vector<vector<bool>> dp(lenp+1, vector<bool>(lens+1, false));
    	     dp[0][0] = true;
    	     for (int i = 1; i <= lenp; ++i) { // i for p
    	         for (int j = 1; j <= lens; ++j) { // j for s
    	             if (p[i-1] != '*' && p[i-1] != '?') {
    	                 dp[i][j] = p[i-1]==s[j-1] ? dp[i-1][j-1]:0;
    	             } else if (p[i-1]=='*') {
    	                 dp[i][0] = dp[i - 1][0]; // "true" even if s is an empty string!
    	                 dp[i][j] = (dp[i-1][j-1]||dp[i][j-1]||dp[i-1][j]);
    	             } else {
    	                 dp[i][j] = dp[i-1][j-1];
    	             }
    	         }
    	     }
    	     
    	     return dp[lenp][lens];
    	 }
    	 
     };

Log in to reply
 

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