Decode Ways

Posted by: lexigrey on: July 17, 2013

• In: leetcode
• Leave a Comment

A message containing letters from A-Z is being encoded to numbers using the A=1, B=2.. Z=26 mapping， 问给一个全是digit的string，有几种decode成字母组合的方式。比如Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

这个题一开始是正常做的，然后就挂掉大的test case了。其实一维数组，问“几种ways”，肯定是要dp的。这题类似于小孩上楼梯，求d[i]有两种情况：

1. 当前这个single digit arr[i]是在1~9之内，说明能组成一个字母，则当前的组合方式(d[i – 1], arr[i])成功，则d[i] = d[i – 1]。不成功，则以i结尾的string没有组合方式，d[i] = 0
2. 当前这个arr[i]是能组成一个10~26的两位数的第二个digit。这样的话，当前的组合(d[i -2], “arr[i – 1]arr[i]”）成功，则d[i] += d[i – 2]。不成功也不归零，因为可能之前single digit的方式成了，所以不动这个d[i]就行了。

public int numDecodings(String s) {
 if (s.length() == 0)
  return 0;
 int[] d = new int[s.length()];
  if (s.charAt(0) - '0' != 0)
   d[0] = 1;
 for (int i = 1; i < s.length(); i++) {
  if (s.charAt(i) - '0' != 0)
   d[i] = d[i - 1];
  else
   d[i] = 0;
  if (canFormTwo(s, i - 1, i + 1))
   d[i] += i > 1 ? d[i - 2] : 1;
 }
 return d[s.length() - 1];
}
boolean canFormTwo(String s, int i, int j) {
 if (j > s.length())
  return false;
 Integer firstTwo = Integer.valueOf(s.substring(i, j));
  return firstTwo > 9 && firstTwo <= 26;
 }

好像其实不用这么大的空间，应该两个变量就够了，一个prev, 一个prevprev，但是没想好，而且懒得想了。以后再说。

Tags: 1WayDP