Decode Ways

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的方法,但是非常繁琐,因为要考虑多种情况(4种),所以直接写一个函数来生成case num,然后用switch case 来做。

4种情况是以下的四种:(考虑当前字符和前一个字符)
1.可以形成2bitvalid的decoding,自己单独也可以形成valid的decode,比如说第一位是1,或者第一位是2,第二位是1~6的数。
2.只能形成两位valid的情况,例如第一位是1或2,而第二位是0,或者第一位是1,第二位是7~9的情况
3.只能形成第二位一个bitvalid的情况,例如第一位不是1和2,第二位不是0,还有第二位是7~9但是第一位不是1和2的情况。
4,无法形成任何valid bit的情况,例如第一位不是1或2,第二位是0的情况。

以上四种办法只要按dp做出递推公式即可,另外dp[1]要单独做因为是initialization的一部分。

public class Solution {
    public int numDecodings(String s) {
        if (s.length() == 0)
            return 0;
        int dp[] = new int[s.length()];
        dp[0] = (s.charAt(0) == '0')? 0 : 1;
        if (s.length () > 1)
        {
            switch (getCase(s.charAt(0), s.charAt(1)))
            {
                case 1: dp[1] = 1;
                        break;
                case 2: dp[1] = 0;
                        break;
                case 3: dp[1] = 2;
                        break;
                case 4: dp[1] = dp[0];
                        break;
            }
        }
        if (s.length() > 2)
        {
            for (int i = 2; i < s.length(); i++)
            {
                switch (getCase(s.charAt(i-1), s.charAt(i)))
                {
                    case 1: dp[i] = dp[i-2];
                            break;
                    case 2: dp[i] = 0;
                            break;
                    case 3: dp[i] = dp[i-1] + dp[i-2];
                            break;
                    case 4: dp[i] = dp[i-1];
                            break;
                }
            }
        }
        return dp[s.length()-1];
    }
    
    int getCase(char c, char d)
    {
        if (d == '0')
        {
            if (c == '1' || c == '2') //forms 10, 20 only 2 bit valid encoding
                return 1;
            else
                return 2; // can not form any valid encoding 
        }
        if (d - '0' < 7)
        {
            if (c == '1' || c == '2') // forms 16, 26, and d itself both 1 bit and 2 bit encoding
                return 3;
            else
                return 4; // forms only 1 bit encoding 
        }
        if (d -'0' >= 7)
        {
            if (c == '1') // forms both 2 bit encoding and 1 bit encoding
                return 3;
            else
                return  4; // forms only 1 bit encoding 
        }
        return 0;
    }
}

Second Submission:

Thought of a simple solution, use Integer.parseInt to validate the string s (length of 1 or 2) to be in the range 1 ~ 26 or not. Code becomes much simpler. DP itself is the same as described above.

public class Solution {
    public int numDecodings(String s) {
        int [] dp = new int [s.length()];
        if (s.length() == 0)
            return 0;
        if (s.length() == 1)
            return isValid(s)? 1: 0;
        if (!isValid(s.substring(0,1)))
            return 0; //if first char is not legal, return false
        dp[0] = 1;
        dp[1] = 0;
        if (isValid(s.substring(0, 2)))
            dp[1] = 1;
        if (isValid(s.substring(1,2)))
            dp[1] += 1;
        for (int i = 2; i &lt; s.length(); i++) {
            if (isValid(s.substring(i-1, i+1)))
                dp[i] = dp[i-2];
            if (isValid(s.substring(i, i+1)))
                dp[i] += dp[i-1];
        }
        return dp[s.length() - 1];
    }
    
    public boolean isValid(String s) {
        if (s.charAt(0) == '0')
            return false;
        if (Integer.parseInt(s)  0)
            return true;
        return false;
            
    }

}

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