The Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping:

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

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

  • "AAJF" with the grouping (1 1 10 6)
  • "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

Check LeetCode link for more details and example input & output.

A Recursive Solution

Below is a straightforward recursive solution.

  public int numDecodings(String s) {
      return numberOfDecodingStartAt(s, 0);
  }

  int numberOfDecodingStartAt(String s, int index) {
      if (index == s.length()) {
          return 1;
      }

      int result = 0;
      if (isChar(s, index, index + 1)) {
          result += numberOfDecodingStartAt(s, index + 1);
      }
      if (index + 2 <= s.length() && isChar(s, index, index + 2)) {
          result += numberOfDecodingStartAt(s, index + 2);
      }
      return result;
  }

  boolean isChar(String s, int start, int end) {
      // "06" cannot be mapped into 'F' since "6" is different from "06".
      if (s.charAt(start) == '0') { 
          return false;
      }

      int code = Integer.parseInt(s.substring(start, end));
      return code > 0 && code < 27; // 1 - 26
  }

Dynamic Programming Solutions

A Top Down Approach

Improve the performance by caching the results of sub problems.

  public int numDecodings(String s) {
      int[] dp = new int[s.length()];
      Arrays.fill(dp, -1);

      return numberOfDecodingStartAt(s, 0, dp);
  }

  int numberOfDecodingStartAt(String s, int index, int[] dp) {
      if (index == s.length()) {
          return 1;
      }

      if (dp[index] != -1) {
          return dp[index];
      }

      int result = 0;
      if (isChar(s, index, index + 1)) {
          result += numberOfDecodingStartAt(s, index + 1, dp);
      }
      if (index + 2 <= s.length() && isChar(s, index, index + 2)) {
          result += numberOfDecodingStartAt(s, index + 2, dp);
      }
      dp[index] = result;
      return result;
  }
  
  boolean isChar(String s, int start, int end) {
      if (s.charAt(start) == '0') {
          return false;
      }

      int code = Integer.parseInt(s.substring(start, end));
      return code > 0 && code < 27; // 1 - 26
  }

A Bottom Up Approach

dp[i] is the sub problem, whose input is the sub string of s, starting at the index i.

  dp[i] = (isChar(s, i, i + 1) ? dp[i + 1] : 0) 
            + (isChar(s, i, i + 2) ? dp[i + 2] : 0)

Base cases:

  • dp[s.length() - 1] = isChar(s, s.length() - 1, s.length()) ? 1 : 0
  • dp[s.length()] = 1, (Try using "12" as the input, you will find dp[2] is 1.)
  public int numDecodings(String s) {
      int dp1 = isChar(s, s.length() - 1, s.length()) ? 1 : 0; // dp[i+1]
      int dp2 = 1; // dp[i+2]
 
      for (int i = s.length() - 2; i >= 0; i--) {
          int tmp = 0;
          if (isChar(s, i, i + 1)) {
              tmp += dp1;
          }
          if (isChar(s, i, i + 2)) {
              tmp += dp2;
          }
          dp2 = dp1;
          dp1 = tmp;
      }
  
      return dp1;
  }
  
  boolean isChar(String s, int start, int end) {
      if (s.charAt(start) == '0') {
          return false;
      }

      int code = Integer.parseInt(s.substring(start, end));
      return code > 0 && code < 27; // 1 - 26
  }