DP with easy understand Java Solution


  • 10
    Y
    public class Solution {
        public int numDecodings(String s) {
            int n = s.length();
            if (n == 0 || s.startsWith("0")) {
                return 0;
            }
            int[] ways = new int[n+1];
            ways[0] = 1;
            ways[1] = 1;
            for (int i = 2; i <= n; i++) {
                int first = Integer.parseInt(s.substring(i-2, i));
                int prev = (first <= 26 && first > 9) ? ways[i-2]:0;
                int plus = (Integer.parseInt(s.substring(i-1, i)) == 0) ? 0:ways[i-1];
                ways[i] = prev + plus;
            }
            return ways[n];
        }
    }

  • 22
    S

    Exact idea as above with some better named variables to follow the logic

    public int numDecodings(String s) {
        
    	if(s== null || s.isEmpty() || s.charAt(0) == '0') return 0;
    	int[] dp = new int[s.length()+1];
    	dp[0] = 1;
    	dp[1] = 1;
    	
    	for(int i = 2 ; i <= s.length() ;i++){
    		int num = Integer.parseInt(s.substring(i-2,i));
    		int twoStepsBehind = (num <= 26 && num >= 10) ? dp[i-2] : 0;
    		int oneStepBehind = (Integer.parseInt(s.substring(i-1,i)) != 0) ? dp[i-1] : 0;
    		dp[i] = twoStepsBehind + oneStepBehind; // can reach here by either hopping 2 steps or 1 step
    	}
    	
    	return dp[s.length()];
    
    }

  • 0

    @sj482 Your solution is fantastic. Here's a mildly refactored version of the same:

    	public int numDecodings(String s) {
    		if (s == null || s.isEmpty()) return 0;
    		int n = s.length();
    		int[] dp = new int[n + 1];
    		dp[0] = 1; // if no characters, there's only 1 decoding
    		if (s.charAt(0) == '0') return 0; // whoops! your first character turned out to be a dud
    		dp[1] = 1; // if 1 character, there's only 1 decoding. We've already vetted it's not a 0
    		for (int i = 2; i <= n; i++) {
    			
    			int numUsingLast2Chars = Integer.parseInt(s.substring(i - 2, i));
    			int numUsingLast1Char = Integer.parseInt(s.substring(i - 1, i));
    
    			if (isValidTwoDigitNumber(numUsingLast2Chars)) {
    				dp[i] += dp[i - 2];
    			}
    			if (isValidOneDigitNumber(numUsingLast1Char)) {
    				dp[i] += dp[i - 1];
    			}
    		}
    
    		return dp[n];
    	}
    
    	private boolean isValidOneDigitNumber(int numUsingLast1Char) {
    		return numUsingLast1Char != 0;
    	}
    
    	private boolean isValidTwoDigitNumber(int numUsingLast2Chars) {
    		return numUsingLast2Chars >= 10 && numUsingLast2Chars <= 26;
    	}
    

Log in to reply
 

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