Straight forward JAVA solution with explanation


  • 0

    Formula: dp[n]=dp[n-1]+dp[n-2]

    Bottom-up solution:
    dp[i], i stand for the number of characters in the string.
    Base case: dp[0] = 1. reason: after we look back to i-2 OR i-1, there's no characters left in the string. So it's valid case.
    Similarly for dp[1] , when we look back, there's 1 character which is the first character in the string, we then check if this character is valid.

    public class Solution {
        public int numDecodings(String s) {
            if(s == null || s.length() == 0) return 0;
            int[] dp = new int[s.length()+1];
            dp[0] = 1;
            dp[1] = (s.charAt(0) == '0')? 0 : 1;
            for(int i = 2; i<= s.length(); i++)
            {
                // check if s.substring(i-2,i) valid
                int val = Integer.parseInt(s.substring(i-2, i));
                dp[i] = (val >= 10 && val <= 26)? dp[i-2]: 0;
                // check if s.substring(i-1, i) valid
                val = Integer.parseInt(s.substring(i-1, i));
                dp[i] += (val == 0) ? 0 : dp[i-1];
            }
            return dp[s.length()];
        }
    

    Time Com­plex­ity: O(n) , Space Com­plex­ity : O(n)


Log in to reply
 

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