Decode Ways

Leave a comment

February 21, 2017 by oneOokay

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.


吃太多肉了最近又…

这题还挺容易想到用dp的,但是要如何简单易懂简洁的写出来对我来说还有点困难…..

首先确认是从string的左边开始扫还是右边开始扫,从左往右扫,那么i为当前考虑的substring的最后一个char. 就只需要考虑从当前char i – 2到i和i-1到i所组成的数字.

对于当前的i考虑两种情况:[i-2,i]是否是一个valid的两位数,[i-1,i]是否是一个valid的一位数.

  • decode opt1: [i-2,i]是一个valid的两位数,把[i-2,i]当成一个valid两位数来decode的话,一共有dp[i-2]种方法,否则是0种.
  • decode opt2: [i-1,i]是一个valid的一位数,把[i-1,i]当成一个一位数来decode的话,一共有dp[i-1]种方法,否则是0种
  • 所以最终结果是:decode opt1 + opt2

有这么些情况吧:

  • 如果string以0开始那么decode ways = 0, 因为invalid;
  • 一位数字==0的时候,decode ways = 0;
  • 能够被decode的两位数字范围在(9, 26]
  • 用s.substring(start, end)来决定是取一个char还是两个char
  • 用Integer.parseInt(str)来把任何string形式的数字转成数字
  • count[0] = 1
  • string.startsWith(string)
public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.startsWith("0")) return 0;
        int len = s.length();
        int[] dp = new int[len + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= len; i ++){
            int twoDigitsvalue = Integer.parseInt(s.substring(i - 2, i));
            int twoDigits = (twoDigitsvalue > 26 || twoDigitsvalue < 10) ? 0 : dp[i - 2];
            int oneDigitValue = Integer.parseInt(s.substring(i - 1, i));
            int oneDigit = oneDigitValue == 0 ? 0 : dp[i - 1];
            dp[i] = twoDigits + oneDigit;
        }
        return dp[len];
    }
Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: