(Java) DP solution that's similar to the WordBreak problem


  • 0
    C
    public class Solution {
        public int numDecodings(String s) {
            int n = s.length();
    
            if (n == 0) return 0;
            if (s.charAt(0) == '0') return 0;
            
            Set<String> set = new HashSet<String>();
            for (int i = 1; i <=26; i++) set.add(Integer.toString(i));
            
            int[] ways = new int[n+1];
            ways[0] = 1;
            ways[1] = 1;
            
            for (int i = 2; i <= n; i++) {
                String str = s.substring(i-2, i);
                if (set.contains(str)) {
                    if(str.equals("20") || str.equals("10")) {
                        ways[i] = ways[i-2];
                    } else {
                        ways[i] = ways[i-1] + ways[i-2];
                    }
                } else {
                    if (Integer.valueOf(str) % 10 == 0) return 0;
                    ways[i] = ways[i-1];
                }
            }
            
            return ways[n];
        }
    }

Log in to reply
 

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