A clear DP solution with java with explanation


  • 0
    S
    public int numDecodings4(String s) {
    	if (s.isEmpty()) {
    		return 0;
    	}
    	int N = s.length();
    	int[] dp = new int[N + 1];
    	dp[N] = 1;
    	for (int i = N - 1; i >= 0; i--) {
    		if (s.charAt(i) == '0')//s[i]不能作為起始字符
    			dp[i] = 0;
    		else if (i <= N - 2
    				&& (s.charAt(i) == '1' || (s.charAt(i) == '2' && s
    						.charAt(i + 1) <= '6'))) {//s[i]可以作為起始字符,並且和s[i+1]可以合併
    			dp[i] = dp[i + 1] + dp[i + 2];
    		} else//s[i]可以作為起始字符,,s[i]和s[i+1]不可以合併
    			dp[i] = dp[i + 1];
    	}
    	return dp[0];
    }

  • 0
    Q

    you don't need an entire array to store all the intermediate results which may cost more time and memory. But your code is really concise


Log in to reply
 

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