Twenty Percent Knowledge: Decode Ways

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

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

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

My Answer:

/**
 * analysis:
 * I thought it is multiplication, then since it adds up conditionally, so better 
 * go with basic addition
 * 1. the numbers that can have two meanings
 * 22, {BB,W}
 * 222, {BBB,BW,WB}
 * ~~~position i-2+22 or i-1+2 when i-1 and i compose a number between 11 and 26 (except 20)
 * 2222, {BBWW,WW,(up to here is position i-1 to current position)BBBB,BWB,WBB(these three are transitioning from position i-1)}
 * 22222 this would be all ways from position i-1 and i-2 if last number has position i
 * so general formular ways[i]=ways[i-1+ways[i-2]
 * it is possible to start from two previous position to transit to current position, because number here is just either 1 digit or 2 digits
 * 
 * 2.if a position has number bigger than 2, then there is only one way to map back to letter
 * 2234
 * 34 is not possible, so it has to be 223(remains all possible combinations) and 4, equivalent to number of ways of 223
 * here i0=1,i1=2,i2=3, i3 is still 3
 * 
 * 3. 0
 * leading 0 is impossible and means wrong input, return 0. mainly because the map has no 0 in it
 * 0,00, 30, 301(30,1 or 3,01 are all invalid)
 * 
 * @author Andrew
 *
 */
public class Solution {

 public static int numDecodings(String s) {
  ///"","0","00", leading with 0
  if (s == null || s.length() == 0 || "0".equals(s.substring(0, 1))) {
   return 0;
  }
  //2,08
  if (s.length() == 1) return 1;

  int[] ways = new int[s.length()];
  char prevChar, curChar;
  int curNum;

  ways[0] = 1;
  ways[1] = 1;
  //for string longer than 2, figure out the first 2 positions possible combinations
  //this might be able to be integrated to the following loop
  if (s.length() >= 2) {
   //impossible situations: 30, 40, only 0 has this problem because it is not in the map
   if (s.charAt(0) > '2' && s.charAt(1) == '0') ways[1] = 0;
   //10 and 20 are valid, and they has only one possible decoding way
   else if ((s.charAt(0) == '1' || s.charAt(0) == '2') && s.charAt(1) == '0') ways[1] = 1;
   //all other numbers such as 11,22 26 are having 2 possible decodings
   else if (Integer.parseInt(s.substring(0, 2)) > 10 && Integer.parseInt(s.substring(0, 2)) <= 26) ways[1] = 2;
  }
  //starting form third position because my basic assumption is ways[i]=ways[i-1]+ways[i-2]
  for (int i = 2; i < s.length(); i++) {
   prevChar = s.charAt(i - 1);
   curChar = s.charAt(i);
   curNum = Integer.parseInt("" + prevChar + curChar);
   //for 20 and 10(0 is position i),i-1 has only one possibility, so it equals ways at i-2
   //this handles numbers between 1-10 in two positions
   if (curChar == '0') {
    ways[i] = ((prevChar == '2' || prevChar == '1') ? ways[i - 2] : 0);
    ways[i - 1] = ways[i]; //i-1 should be same as i
   }
   //this is for numbers that has two possible ways to decode
   else if (curNum > 10 && curNum <= 26) ways[i] = ways[i - 2] + ways[i - 1];
   else //other situation has only 1 possible way to decode, so current ways of decoding is
   //equals to previous ways of decoding
   ways[i] = ways[i - 1];

  }
  return ways[s.length() - 1];
 }



 public static void main(String[] args) {
  //  System.out.println(numDecodings("99")    );
  //  System.out.println(numDecodings("27")    );
  //  System.out.println(numDecodings("301")    );
  //  System.out.println(numDecodings("08")    );
  System.out.println(numDecodings("110"));
  System.out.println(numDecodings("920"));
  System.out.println(numDecodings("20"));
 }

}

Test cases:

import static org.junit.Assert.*;

import org.junit.Test;


public class WaysDecodeTest {

 @Test
 public void testNumDecodings1() {
  int actual = Solution.numDecodings("99");
  assertEquals(1, actual);
 }
 @Test
 public void testNumDecodings2() {
  int actual = Solution.numDecodings("301");
  assertEquals(0, actual);
 }
 @Test
 public void testNumDecodings3() {
  int actual = Solution.numDecodings("27");
  assertEquals(1, actual);
 }
 @Test
 public void testNumDecodings4() {
  int actual = Solution.numDecodings("08");
  assertEquals(0, actual);
 }
 @Test
 public void testNumDecodings5() {
  int actual = Solution.numDecodings("12");
  assertEquals(2, actual);
 }
 
 @Test
 public void testNumDecodings6() {
  int actual = Solution.numDecodings("121");
  assertEquals(3, actual);
 }
 @Test
 public void testNumDecodings7() {
  int actual = Solution.numDecodings("2222");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings8() {
  int actual = Solution.numDecodings("22222");
  assertEquals(8, actual);
 }
 @Test
 public void testNumDecodings9() {
  int actual = Solution.numDecodings("22229");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings10() {
  int actual = Solution.numDecodings("222292");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings11() {
  int actual = Solution.numDecodings("2222920");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings12() {
  int actual = Solution.numDecodings("110");
  assertEquals(1, actual);
 }
 @Test
 public void testNumDecodings13() {
  int actual = Solution.numDecodings("20");
  assertEquals(1, actual);
 }
}

Twenty Percent Knowledge

Saturday, June 27, 2015

Decode Ways

No comments: