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 a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

难度:medium

题目:一则数字消息由A到Z的字符编码,字符与数字的匹配关系如下

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定非空字符串仅包含数字,判断它由多少种解码方式。

思路:动态规划,首先来分解一下问题

状态转移方程

f(n) = f(n - 1) + f(n - 2) 当前字符在[1,9] 之间,且当前字符与前一字符组成的数在[11,19][21,26]之间
f(n) = f(n - 1) 当前字符与前一字符组成的数不在[1,9][11,26]之间
f(n) = f(n - 2) 当前字符与前一字符组成的数为10或20

根据此方程可以使用递归实现,这是将想法实施的第一步。

第二步优化,将递归实现转成迭代实现。

Runtime: 5470 ms, faster than 0.99% of Java online submissions for Decode Ways.

Memory Usage: 50.2 MB, less than 0.97% of Java online submissions for Decode Ways.

class Solution {
    public int numDecodings(String s) {
        return numDecodings(s, s.length());
    }
    
    // length > 0
    private int numDecodings(String s, int length) {
        // 字符不为空 初始化length0 为1
        if (0 == length) {
            return 1;
        }
        if (1 == length) {
            if (Integer.parseInt(s.substring(length - 1, length)) > 0) {
                return 1;
            }
            return 0;
        }
        
        int last = length - 1;
        int prev = last - 1;
        int valLast = Integer.parseInt(s.substring(last, last + 1));
        int valPrev = Integer.parseInt(s.substring(prev, prev + 2));
        if (10 == valPrev || 20 == valPrev) {
            return numDecodings(s, length - 2);
        } else if (valPrev >= 10 && valPrev <= 26) {
            return numDecodings(s, length - 1) + numDecodings(s, length - 2);
        } 
        
        if (valLast > 0 && valLast < 10) {
            return numDecodings(s, length - 1);
        }
        
        return 0;
    }
}

Runtime: 3 ms, faster than 43.60% of Java online submissions for Decode Ways.

Memory Usage: 34.6 MB, less than 3.09% of Java online submissions for Decode Ways.

class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }
        int p = 1, q = 1, result = 1;
        for (int i = 1; i < s.length(); i++) {
            int num1 = s.charAt(i) - '0';
            int num2 = Integer.valueOf(s.substring(i - 1, i + 1));
            if (num2 == 10 || num2 == 20) {
                result = p;
            } else if (10 < num2 && num2 <= 26) {
                result = p + q;
            } else if (num1 > 0 && num1 < 10) {
                result = q;
            } else {
                return 0;
            }
            
            p = q;
            q = result;
        }
        
        return result;
    }
}

原文 

https://segmentfault.com/a/1190000018125145

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 91. Decode Ways

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址