Straight forward way without caring about case '0'


  • 0
    D

    The basic idea is we can compose all possible numbers in the string format ["1","2",....,"26"] so the question came to a DP question with

    f(n) = f(n-1) (if char[n-1] is valid 1-9) + f(n-2) (if substring [n-2,n] is in the set.

    class Solution {
        public int numDecodings(String s) {
            Set<String> vals = new HashSet<String>();
            
            for (int i = 1; i <= 26; i++) {
                vals.add(i + "");
            }
            
            int[] dp = new int[s.length() + 1];
            
            dp[0] = s.length() == 0 ? 0 : 1;
            
            for (int i = 1; i <= s.length(); i++) {
                if (i > 1 && vals.contains(s.substring(i-2, i))) {
                    dp[i] += dp[i-2];
                }
                
                if (s.charAt(i-1) >= '1' && s.charAt(i-1) <= '9') {
                    dp[i] += dp[i-1];
                }
            }
            
            return dp[s.length()];
        }
    }
    

Log in to reply
 

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