package com.freetymekiyan.algorithms.level.medium;

/**
 * A message containing letters from A-Z is being encoded to numbers using the following mapping:
 * <p>
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * Given an encoded message containing digits, determine the total number of ways to decode it.
 * <p>
 * For example,
 * Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
 * <p>
 * The number of ways decoding "12" is 2.
 * <p>
 * Company Tags: Microsoft, Uber, Facebook
 * Tags: Dynamic Programming, String
 */
class DecodeWays {

    public static void main(String[] args) {
        DecodeWays d = new DecodeWays();
        System.out.println(d.numDecodings("1029"));
    }

    /**
     * DP. O(n) Time, O(n) Space.
     * Suppose the length of the String is n.
     * Recurrence relation:
     * number of decode ways at length n related to number of decode ways at previous lengths.
     * If we can decode the last digit, then ways[n] += ways[n-1].
     * If we can decode the last two digits, then ways[n] += ways[n-2].
     * Base case:
     * ways[0] = 1, means only one way when string length is zero.
     * ways[1] = 0 or 1, depending on the only digit is 0 or non-zero.
     */
    public static int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();
        int[] ways = new int[len + 1];
        // Base cases
        ways[0] = 1;
        ways[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i <= len; i++) {
            int code1 = Integer.valueOf(s.substring(i - 1, i));
            int code2 = Integer.valueOf(s.substring(i - 2, i));
            // System.out.println(code2);
            ways[i] = (code1 != 0 ? ways[i - 1] : 0) + (code2 <= 26 && code2 > 9 ? ways[i - 2] : 0);
        }
        return ways[len];
    }

    /**
     * DP. O(n) Time, O(1) Space.
     * Don't need an array since we only need previous two results.
     * Remember to update those results.
     */
    public int numDecodingsB(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();
        int prev1 = 1;
        int prev2 = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i <= len; i++) {
            int code1 = Integer.valueOf(s.substring(i - 1, i)); // 1 digit
            int code2 = Integer.valueOf(s.substring(i - 2, i)); // 2 digits
            int temp = prev2;
            prev2 = (code1 != 0 ? prev2 : 0) + (code2 <= 26 && code2 > 9 ? prev1 : 0);
            prev1 = temp;
        }
        return prev2;
    }
}

@@ -535,16 +535,23 @@
 ing%0A */%0A
+public 
 class De
@@ -564,153 +564,8 @@
 ys %7B
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        DecodeWays d = new DecodeWays();%0A        System.out.println(d.numDecodings(%221029%22));%0A    %7D
 %0A%0A  
@@ -572,32 +572,43 @@
   /**%0A     * DP.
+ Bottom-up.
  O(n) Time, O(n)
@@ -787,35 +787,25 @@
 ths.%0A     * 
-If we can d
+D
 ecode the la
@@ -798,24 +798,31 @@
  Decode the 
+single 
 last digit, 
@@ -859,19 +859,9 @@
   * 
-If we can d
+D
 ecod
@@ -882,16 +882,29 @@
  digits,
+ if possible,
  then wa
@@ -939,16 +939,17 @@
 ase case
+s
 :%0A     *
@@ -1003,20 +1003,17 @@
 ngth is 
-zero
+0
 .%0A     *
@@ -1100,15 +1100,8 @@
 lic 
-static 
 int 
@@ -1308,24 +1308,89 @@
 ways%5B0%5D = 1;
+ // Think about ways%5B2%5D when code2 is valid, ways%5B0%5D should be 1.
 %0A        way
@@ -1597,50 +1597,8 @@
 ));%0A
-            // System.out.println(code2);%0A
     
@@ -1755,16 +1755,38 @@
    * DP.
+ Bottom-up. Optimized.
  O(n) Ti
@@ -2168,32 +2168,66 @@
 i %3C= len; i++) %7B
+ // i is the length of the string.
 %0A            int
@@ -2281,16 +2281,21 @@
 ; //
+ Last
  1 digit
 %0A   
@@ -2290,16 +2290,17 @@
  1 digit
+.
 %0A       
@@ -2358,16 +2358,21 @@
  i)); //
+ Last
  2 digit
@@ -2372,16 +2372,17 @@
 2 digits
+.
 %0A       
@@ -2399,24 +2399,80 @@
 emp = prev2;
+ // Store prev2 first. Otherwise it will be overwritten.
 %0A           

update Decode Ways