Lexi's Leetcode solutions

Decode Ways

Posted on: July 17, 2013

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:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog Stats

  • 222,234 hits
July 2013
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
293031  
%d bloggers like this: