[LintCode/LeetCode] Decode Ways [String to Integer

andong777 发布于2019-08-14 15:44 / 2228人阅读

摘要：用将子字符串转化为，参见和的区别然后用动规方法表示字符串的前位到包含方法的个数。最后返回对应字符串末位的动规结果。

Problem

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.

Example

Given encoded message 12, it could be decoded as AB (1 2) or L (12).
The number of ways decoding 12 is 2.

Note

用parseInt将子字符串转化为int，参见parseInt和valueOf的区别；
然后用动规方法：
dp[i]表示字符串s的前i位（0到i-1）包含decode方法的个数。
若前一位i-2到当前位i-1的两位字符串s.substring(i-2, i)对应的数字lastTwo在10到26之间，则当前位dp[i]要加上这两位字符之前一个字符对应的可能性：dp[i-2];
若当前位i-1的字符对应1到9之间的数字（不为0），则当前dp[i]要加上前一位也就是第i-2位的可能性：dp[i-1]。
最后返回对应字符串s末位的动规结果dp[n]。

Solution updated 2018-9

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;
        int n = s.length();
        int[] dp = new int[n+1];
        dp[0] = 1;                                                  //if the first two digits in [10, 26]
        dp[1] = s.charAt(0) == "0" ? 0 : 1;
        for (int i = 2; i <= n; i++) {
            if (s.charAt(i-1) != "0") dp[i] += dp[i-1];             //XXX5X
            int lastTwo = Integer.parseInt(s.substring(i-2, i));
            if (lastTwo >= 10 && lastTwo <= 26) dp[i] += dp[i-2];   //XXX10X
        }
        return dp[n];
    }
}

私有云专线服务 Ways integer decode integer类型

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65974.html

[LintCode/LeetCode] Jump Game I & II

摘要：建立动规数组，表示从起点处到达该点的可能性。循环结束后，数组对所有点作为终点的可能性都进行了赋值。和的不同在于找到最少的步数。此时的一定是满足条件的最小的，所以一定是最优解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...

rose 2019-08-14 15:27 评论0 收藏0
[LintCode/LeetCode] Binary Tree Serialization

摘要：这里要注意的是的用法。所以记住，用可以从自动分离出数组。跳过第一个元素并放入数组最快捷语句建立的用意记录处理过的结点并按处理所有结点和自己的连接下面先通过判断，再修改的符号的顺序，十分巧妙更轻便的解法 Problem Design an algorithm and write code to serialize and deserialize a binary tree. Writin...

keithyau 2019-08-14 15:12 评论0 收藏0
91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following A -> 1 B -> 2 ... Z -> 26 For example, Given encoded message 12, it could be decoded as AB (1 2) or L (12). The n...

macg0406 2019-08-14 18:05 评论0 收藏0
[LintCode/LeetCode] Integer Replacement

Problem Given a positive integer n and you can do operations as follow: 1.If n is even, replace n with n/2.2.If n is odd, you can replace n with either n + 1 or n - 1. What is the minimum number of re...

fyber 2019-08-16 12:44 评论0 收藏0
[LintCode/LeetCode] Min Stack/Max Stack

Problem Implement a stack with min() function, which will return the smallest number in the stack. It should support push, pop and min operation all in O(1) cost. Example push(1)pop() // return 1pus...

GHOST_349178 2019-08-14 15:14 评论0 收藏0