DP Solution: both Forward & Backward


  • 2
    R
    • First, the backward solution

      public int numDecodings(String s) {

       // validate the input and take care of special cases
       if (null == s || s.length() == 0) return 0;
      
       // let's DP~
       int n = s.length();        
       int[] numDecodingsFromIndex = new int[n + 1];
      
       // initialize the last 2 element of numDecodingsFromIndex[]
       numDecodingsFromIndex[n] = 1;
       numDecodingsFromIndex[n - 1] = Integer.parseInt(s.substring(n - 1)) != 0 ? 1 : 0;
      
       // backwards
       for (int j = n - 2; j >= 0; j--) {
      
           int thisDigit = Integer.parseInt(s.substring(j, j+1));
      
           if (0 == thisDigit) {
               continue;
           } else {
               // when 0 != thisDigit, we can cut at this position
               numDecodingsFromIndex[j] = numDecodingsFromIndex[j + 1];
      
               if (Integer.parseInt(s.substring(j, j + 2)) <= 26) {
                   numDecodingsFromIndex[j] += numDecodingsFromIndex[j + 2];
               }
           }
       }
       return numDecodingsFromIndex[0];
      

      }


    • Then, the forward solution. Coming up with the forward version is very straightforward, especially for DP-newbies like me.

      public int numDecodings(String s) {

       // validate the input
       if (null == s || s.length() == 0) return 0;
       
       // dp: remember every result that has been calculated
       int[] numDecodingsFromIndex = new int[s.length()];
       // -1 means "has not been calculated yet"
       for (int i = 0; i < numDecodingsFromIndex.length; i++) {
           numDecodingsFromIndex[i] = -1;
       }
      
       return numDecodings(s, 0, numDecodingsFromIndex);      
      

      }

      private int numDecodings(final String s, int startIndex, int[] numDecodingsFromIndex) {

       // if we have crossed the finish line
       if (startIndex >= s.length()) {
           return 1;
       }
      
       // if the result is already there, just get it
       if (numDecodingsFromIndex[startIndex] != -1) {
           return numDecodingsFromIndex[startIndex];
       }
      
       // if not, we need to calculate it
       numDecodingsFromIndex[startIndex] = 0;
      
       // the first digit should be between 1~9
       if (Integer.parseInt(s.substring(startIndex, startIndex + 1)) != 0) {
      
           numDecodingsFromIndex[startIndex] = numDecodings(s, startIndex+1, numDecodingsFromIndex);
      
           // if the first two digits are between 1~26, then we get a second cut position
           if ((startIndex+1 < s.length()) && (Integer.parseInt(s.substring(startIndex, startIndex + 2)) <= 26)) {
               numDecodingsFromIndex[startIndex] += numDecodings(s, startIndex + 2, numDecodingsFromIndex);
           }
       }
      
       return numDecodingsFromIndex[startIndex];
      

      }


  • 0
    S

    Please update code format.

    Select all code then click on the {} button to preserve code formatting.


  • 0
    R

    I have tried many times. But it just ignored the first and last line. Do you know why?


Log in to reply
 

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