Leet Code: 91. Decode Ways

 https://leetcode.com/problems/decode-ways/ 

import java.util.Arrays;
import java.util.HashMap;

public class LeetCode_91_DecodeWays {

    public static void display(int[] dp) {
        for (int i : dp) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        String s = "21654";
        System.out.println(numDecodings(s));
    }

    public static int numDecodings(String s) {
        int x = recursion(s);
        //return recursionMemo(s, new HashMap<String, Integer>());

        //return recursionArray(s, 0);
        int[] dp = new int[s.length() + 1];
        Arrays.fill(dp, -1);
        //int x = recursionArrayMemo(s, 0, dp);
        //int x = recursionArrayTabulation(s, 0, dp);
        display(dp);
        return x;

    }

    public static int recursion(String s) {
        if (s.length() == 0)
            return 1;

        int sum = 0;
        int code = s.charAt(0) - '0';

        if (code == 0) {
            return 0;
        }

        sum += recursion(s.substring(1));


        if (s.length() > 1) {
            // String secondString = s.substring(0, 2);
            // int secondCode = Integer.parseInt(secondString);

            code = (code * 10) + (s.charAt(1) - '0');


            if (code <= 26) {
                sum += recursion(s.substring(2));
            }

        }

        return sum;

    }

    public static int recursionMemo(String s, HashMap<String, Integer> dp) {
        if (s.length() == 0) {
            dp.put(s, 1);
            return 1;
        }

        if (dp.containsKey(s)) return dp.get(s);

        int sum = 0;
        int code = s.charAt(0) - '0';

        if (code == 0) {
            dp.put(s, 0);
            return 0;
        }

        sum += recursionMemo(s.substring(1), dp);


        if (s.length() > 1) {
            // String secondString = s.substring(0, 2);
            // int secondCode = Integer.parseInt(secondString);

            code = (code * 10) + (s.charAt(1) - '0');


            if (code <= 26) {
                sum += recursionMemo(s.substring(2), dp);
            }

        }

        dp.put(s, sum);
        return sum;

    }

 private static int recursionArray(String s, int idx) {
        if (idx == s.length())
            return 1;

        int ans = 0;
        int n = s.charAt(idx) - '0';
        if (n == 0)
            return 0;

        ans += recursionArray(s, idx + 1);

        if (idx < s.length() - 1) {
            n = (n * 10) + (s.charAt(idx + 1) - '0');
            if (n <= 26) {
                ans += recursionArray(s, idx + 2);
            }

        }

        return ans;
    }

    private static int recursionArrayMemo(String s, int idx, int[] dp) {
        if (idx == s.length())
            return dp[idx] = 1;

        if (dp[idx] != -1) return dp[idx];
        int ans = 0;
        int n = s.charAt(idx) - '0';
        if (n == 0)
            return dp[idx] = 0;

        ans += recursionArrayMemo(s, idx + 1, dp);

        if (idx < s.length() - 1) {
            n = (n * 10) + (s.charAt(idx + 1) - '0');
            if (n <= 26) {
                ans += recursionArrayMemo(s, idx + 2, dp);
            }

        }

        return dp[idx] = ans;
    }

    private static int recursionArrayTabulation(String s, int IDX, int[] dp) {
        for (int idx = s.length(); idx >= 0; idx--) {

            if (idx == s.length()) {
                dp[idx] = 1;
                continue;
            }

            //if (dp[idx] != -1) return dp[idx];
            int ans = 0;
            int n = s.charAt(idx) - '0';
            if (n == 0) {
                dp[idx] = 0;
                continue;
            }

            ans += dp[idx + 1];//recursionArrayTabulation(s, idx + 1, dp);

            if (idx < s.length() - 1) {
                n = (n * 10) + (s.charAt(idx + 1) - '0');
                if (n <= 26) {
                    ans += dp[idx + 2];//recursionArrayTabulation(s, idx + 2, dp);
                }

            }

            dp[idx] = ans;
        }
        return dp[IDX];
    }

}