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

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

    震惊

    震惊

编辑推荐
原题: A message containing letters from A-Z is being encoded to numbers using the following
SELECT G.PO_ID, G.PROD_ID, G.UNIT_ID, G.PO_SCHD_DATE, SUM(PO_QTY) PO_QTY, SUM(DECODE(G.PO_STA
编码格式主要有:Unicode、utf-8、gbk、utf-16等 unicode是utf-8、gbk等的父编码,所有子编码都可以
DECODE函数是ORACLE PL/SQL是功能强大的函数之一,目前还只有ORACLE公司的SQL提供了此函数,其他数
It’s a very good idea to find different ways of saying the same thing to avoid repeated use
题目 A message containing letters from A-Z is being encoded to numbers using the following ma
http://www.wikihow.com/Install-Java-on-Linux Manual Non-RPM Method This is the generic method
From http://www.notebooks.com/2010/01/17/three-ways-to-sync-browser-bookmarks/ Many people us
http://www.wikihow.com/Install-Java-on-Linux Manual Non-RPM Method This is the generic method
decode(待比较的对象,如果为这个,那么结果为这个,否则结果是这个) 表issueNew.xml中 字段commandS
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号