当前位置:首页 » JAVA技术教程

leetcode-91.+Decode+Ways

2016-12-26 09:32 本站整理 浏览(4)

leetcode-91. 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.

做这题的时候我忘记考虑一个问题:

比如222,这种情况实际上只有[2,2,2][2,22][22,2]这三种情况,我最开始判断的时候实际上是按照当前的i的数字和i+1的数字来判断的只要是10-26之间都判断c=c*2,这样就是2*2所以是4个。判断出错。所以这里实际上要加一个flag来维护i-1的情况

[code]public class Solution {
    public int numDecodings(String s) {
        if(s==null || s.length()<1)return 0;
        int c = 1;
        boolean flag = true;
        for(int i = 0; i < s.length();i++){
            if((s.charAt(i)=='1' && i+1<s.length()) || (s.charAt(i)=='2' && i+1< s.length() && s.charAt(i+1)<'7')){
                if(flag){
                    c *= 2;
                }else{
                    c *= 2;
                    c--;
                }
                flag = false;
            }else{
                flag = true;
            }
        }
        return c;
    }
}