How to resolve the problem of time limit exceeded?


  • 0
    J

    Last executed input: "101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010"

    public class Solution {
        public int numDecodings(String s){
            if(s.equals("")){
                return 0;
            }
    	char[] cArr = s.toCharArray();
    	return num(cArr,0);
     }
    
     private int num(char[] arr,int index){
    	if(arr[index] == '0'){
    		return 0;
    	}
    	if(index < arr.length-2){
    		if((arr[index]-48)*10+arr[index+1]-48 <= 26){
    			return num(arr,index+1)+num(arr,index+2);
    		}else{
    			return num(arr,index+1);
    		}
    	}
    	if(index == arr.length-2){
    		if((arr[index]-48)*10+arr[index+1]-48 <= 26){
    			return num(arr,index+1)+1;
    		}else{
    			return num(arr,index+1);
    		}
    	}
    	if(index==arr.length-1){
    		if(arr[index] == '0'){
    			return 0;
    		}
    		return 1;
    	}
    	return 0;
     }
    }

  • 0
    J

    Please help,what is the problem with my solution?


  • 0
    C

    Your solution does a lot of duplicate computation by using recursion here. It's similar when you try to calculate fibonacci number with recursion. I think there are two ways to speed up your solution:

    1. Use a hash map to memorize the intermediate result and use it in the recursion.
    2. Throw recursion away, use DP.

Log in to reply
 

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