Help with "Time Limit Exceeded" error


  • 1
    A

    Hi,

    I've been working on the "Decade Way" problem for a while. I've tested my code, and I think it works. However, OJ always tells me "Time Limit Exceeded". Any help is appreciated.

    int numDecodings(string s) {
      // IMPORTANT: Please reset any member data you declared, as
      // the same Solution instance will be reused for each test case.
    
      if(s.size() == 1 || s.size() == 0) {
        return 1;
      } else if(s.size() == 2) {
        if(s[0] == '1') {
          return 2;
        } else if (s[0] == '2') {
          if( s[1] != '7' && s[1] != '8' && s[1] != '9') {
          return 2;
          } else {
            return 1;
          }
        } else {
          return 1;
        }
      } else {
        int num = 0;
        if(s[0] == '1') {
          num += numDecodings(s.substr(1)) + numDecodings(s.substr(2));
        } else  if(s[0] == '2') {
          if( s[1] != '7' && s[1] != '8' && s[1] != '9') {
            num += numDecodings(s.substr(1)) + numDecodings(s.substr(2));
          } else {
          num += numDecodings(s.substr(1));
          }
        } else {
          num += numDecodings(s.substr(1));
        }
      return num;
      }
    }

  • 3
    P

    You can use dynamic programming to remember some of the result.

    class Solution {
    public:
    	int* dp;
    	bool* vis;
    
    	int numDecodings(string s) {
    		// IMPORTANT: Please reset any member data you declared, as
    		// the same Solution instance will be reused for each test case.
    		if(s.size()==0) return 0; /*!< special judge */
    		dp = new int[s.size()]; /*!< dp */
    		vis = new bool[s.size()]; /*!< dp flag */
    		memset(vis,0,s.size()*sizeof(bool)); /*!< memset to 0 */
    		int ans = numDecodingsHelperFunction(s,0); /*!< the function that do the actual job */
    		delete[] dp; /*!< release */
    		delete[] vis; /*!< release */
    		return ans;
    	}
    
    	int numDecodingsHelperFunction(const string& s, int index) {
    		if(index == s.size())
    			return 1;  /*!< special judge */
    		if(vis[index])
    			return dp[index]; /*!< the result has been calculated previously */
    		vis[index] = true; /*!< set the flag */
    		if(s[index] == '0') { /*!< special judge, no decodings can start with 0 */
    			dp[index] = 0; /*!< dp */
    			return 0;
    		}
    		if(index == s.size()-1) { /*!< special judge, there is always only 1 way to decode 1-digit number */
    			dp[index] = 1; /*!< dp */
    			return 1;
    		}
    		int num = 0;
    		if(s[index] == '1') { /*!< start with 1 */
    			num += numDecodingsHelperFunction(s,index+1) + numDecodingsHelperFunction(s,index+2);
    		} else  if(s[index] == '2') { /*!< start with 2 */
    			if( s[index+1] != '7' && s[index+1] != '8' && s[index+1] != '9') {
    				num += numDecodingsHelperFunction(s,index+1) + numDecodingsHelperFunction(s,index+2); /*!< end with 0-6 */
    			} else { /*!< ended with 7-9 */
    				num += numDecodingsHelperFunction(s,index+1);
    			}
    		} else { /*!< start with 3-9 */
    			num += numDecodingsHelperFunction(s,index+1);
    		}
    		dp[index] = num; /*!< dp */
    		return num;
    	}
    };

  • 0
    M

    I got the same result first, before I commited this type of code, I knew time would be exceeded because there are too many times which computed same string. Obviously, it's a DP problem as the guy porker2008 said, to solve this type of problems, we can cache the result while processing as porker2008's code, but the best way is to construct from bottom-up rather than top-down, so we just need constant space and linear time.

    int numDecodings(string s) {
        int len = s.length();
        if(len==0||s[0]=='0') return 0;//empty string and first '0' cannot be decoded.
        if(len==1) return s[0]>'0'?1:0;//only non-zero could be decoded while the length is 1.
        int n_1,n_2,result,j=len-1;//n_1,n_2 stand for the f(n-1),f(n-2)
        n_1=s[j]>'0'?1:0;
        for(j-=1;j>=0;j--){
            if(s[j]<'3'&&s[j]>'0'){
                if(s[j+1]>'0'&&((s[j]=='2'&&s[j+1]<'7')||s[j]=='1')){
                    result = n_1+(j==len-2?1:n_2);
                }
                else if(s[j+1]=='0'){
                    result = (j==len-2?1:n_2);
                }
                else{
                    result = n_1;
                }
            }
            else if(s[j+1]=='0'){
                return 0;
            }
            else{
                result = n_1;
            }
            n_2=n_1;
            n_1=result;
        }
        return result;
    }

  • 0
    G
    This post is deleted!

  • 0
    S

    Could you please post a better answer with algorithm explanation and code comment?


  • 19
    S

    for string processing problems with AC rate less than 20%, TLE is guaranteed for recursive method.
    You could always seek to use DP to cut down time complexity, and rolling variables cut down space requirement. Below is my DP code with constant space.

    int numDecodings(string s) {
        if(!s.size()||s[0]=='0')return 0;
        int cur_2 = 1,cur_1 = 1,cur = 0;
        
        for(int i = 2;i<=s.size();i++){
            if(s[i-1]!='0')cur+=cur_1;
            if(s[i-2]=='1'||(s[i-2]=='2'&&s[i-1]<'7'))cur+=cur_2;
            cur_2 = cur_1;
            cur_1 =  cur;
            cur = 0;
        }
        return cur_1;
    }

  • 0
    S
    class Solution {
    public:
        int numDecodings(string s) {
            if (s.length() == 0) return 0;
            if (s.length() == 1) {
                if (s[0] == '0') return 0;
                else return 1;
            }
            vector<int> num_vec(s.length()+1, 0);
            num_vec[0] = 1;
            if (s[0] == '0') num_vec[1] = 0;
            else num_vec[1] = 1;
            int i;
            for (i = 1; i < s.length(); i++) {
                if (s[i] != '0') num_vec[i+1] += num_vec[i];
                if (atoi(s.substr(i-1, 2).c_str()) <= 26 && atoi(s.substr(i-1, 2).c_str()) > 0 && s[i-1] != '0') 
                    num_vec[i+1] += num_vec[i-1];
            }
            return num_vec[i];
        }
    };
    

    This is my code using DP.


  • 0
    D

    simply recursive will re-compute many duplicate cases, for example, for 123XXXX, you'll comput 3XXXX first in A-B-3XXXX(1-2-3XXXX), then again in l-3XXXX(12-3XXXX), you can add a cache to avoid duplications.


Log in to reply
 

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