91. Decode Ways.md

91. Decode Ways

---

leetcode Daily Challenge on December 26th, 2020.

leetcode-cn Daily Challenge on April 21th, 2021.

---

Difficulty : Medium

Related Topics : DynamicProgramming、String

---

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

---

Solution

• mine
  • Java

    • Dynamic Programming Runtime: 2 ms, faster than 67.18%, Memory Usage: 40.7 MB, less than 5.03% of Java online submissions

      // O(N)time O(N)space
      // N = s.length()
      // 1234510215154542044513155431015454
      // 12345 10 21515454 20 4451315543 10 15454
      // beacause 10 20 is just one type
      // so res  = numDecodings(12345) * numDecodings(21515454) * numDecodings(4451315543) * numDecodings(15454)
      // if not contain 10 and 20 but contains 0, we return 0.
      // because 0/30/40... can not be decode
      
      public int numDecodings(String s) {
          int m = s.indexOf("10");
          int n = s.indexOf("20");
          if (m != -1 || n != -1) {
              int max = Math.max(m, n);
              m = Math.min(m, n);
              n = max;
              int start = 0;
              int res = 1;
              if (m != -1) {
                  if (start != m) {
                      res *= numDecodings(s.substring(start, m));
                  }
                  start = m + 2;
              }
              if (n != start) {
                  res *= numDecodings(s.substring(start, n));
              }
              start = n + 2;
              if (start != s.length()) {
                  res *= numDecodings(s.substring(start));
              }
              return res;
          } else if (s.contains("0")) {
              return 0;
          }
          char[] arr = s.toCharArray();
          if (arr[0] == '0') {
              return 0;
          }
          if (arr.length == 1) {
              return 1;
          }
          int len = arr.length;
          int[] dp = new int[len + 1];
          dp[0] = 1;
          dp[1] = 1;
          for (int i = 1; i < len; i++) {
              int sum = (arr[i - 1] - '0') * 10 + (arr[i] - '0');
              if (sum <= 26 && sum > 10) {
                  dp[i + 1] = dp[i] + dp[i - 1];
              } else {
                  dp[i + 1] = dp[i];
              }
          }
          return dp[len];
      }
      

    • Runtime: 1 ms, faster than 93.83%, Memory Usage: 37.2 MB, less than 81.51% of Java online submissions

      // O(N)time
      // O(N)space
      public int numDecodings(String s) {
          char[] arr = s.toCharArray();
          if(arr[0] == '0') return 0;
          
          int len = arr.length;
          int[] dp = new int[len + 1];
          dp[0] = dp[1] = 1;
          for(int i = 2; i <= len; i++){
              int pp = arr[i - 2] - '0';
              int p = arr[i - 1] - '0';
              if(p == 0 && pp == 0) break;
              if(pp == 0) dp[i] = dp[i -1];
              else if(pp * 10 + p > 26 && p == 0) break;
              else if(p == 0) dp[i] = dp[i - 2];
              else if(pp * 10 + p > 26) dp[i] = dp[i - 1];
              else dp[i] = dp[i - 1] + dp[i - 2];
          } 
          return dp[len];
      }
      

---

• the most votes

  • DP Bottom-UP Runtime: 2 ms, faster than 67.18%, Memory Usage: 39 MB, less than 47.39% of Java online submissions

    // O(N)time O(N)space
    // N = s.length()
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) != '0' ? 1 : 0;
        for (int i = 2; i <= n; i++) {
            int first = Integer.valueOf(s.substring(i - 1, i));
            int second = Integer.valueOf(s.substring(i - 2, i));
            if (first >= 1 && first <= 9) {
                dp[i] += dp[i - 1];
            }
            if (second >= 10 && second <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
    

  • DP Top-Down Runtime: 1 ms, faster than 97.76%, Memory Usage: 37.9 MB, less than 70.01% of Java online submissions

    // O(N)time O(N)space
    // N = s.length()
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) return 0;
    
        int[] memo = new int[n + 1];
        memo[n] = 1;
        memo[n - 1] = s.charAt(n - 1) != '0' ? 1 : 0;
    
        for (int i = n - 2; i >= 0; i--) {
            if (s.charAt(i) != '0') {
                memo[i] = (Integer.parseInt(s.substring(i, i + 2)) <= 26) ? memo[i + 1] + memo[i + 2] : memo[i + 1];
            }
        }
        return memo[0];
    }
    

---