当前位置:首页 > 开发 > 编程语言 > 编码 > 正文

Decode Ways

发表于: 2015-07-16   作者:hcx2013   来源:转载   浏览:
摘要: 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, det

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.

 

public class Solution {
    public int numDecodings(String s) {
    	if (s.length() == 0) {
    		return 0;
    	}
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        if (isValid(s.substring(0, 1))) {
        	dp[1] = 1;
        } else {
        	dp[1] = 0;
        }
        for (int i = 2; i <= s.length(); i++) {
        	if (isValid(s.substring(i-1, i))) {
        		dp[i] = dp[i-1];
        	} 
        	if (isValid(s.substring(i-2, i))) {
        		dp[i] += dp[i-2];
        	}
        }
        return dp[s.length()];
    }

	private boolean isValid(String substring) {
		if (substring.charAt(0) == '0') {
			return false;
		}
		int parseInt = Integer.parseInt(substring);
		return parseInt>0 && parseInt<27;
	}
}

 

Decode Ways

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号