[Swift]LeetCode91.解码方法|DecodeWays

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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).

一条包含字母 A-Z 的消息通过以下方式进行了编码：

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

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

8ms

 1 class Solution {
 2     func numDecodings(_ s: String) -> Int {
 3     if s.isEmpty || s[s.startIndex] == "0" { return 0 }
 4     if s.count == 1 { return 1 }
 5     var count = 1, last = 1
 6     var i = s.index(after: s.startIndex)
 7     while i < s.endIndex {
 8         var cur = 0
 9         if s[i] > "0" {
10             cur += count
11         }
12         if s[s.index(before: i)] == "1" || (s[s.index(before: i)] == "2" && s[i] <= "6") {
13             cur += last
14         }
15         last = count
16         count = cur
17         if last == 0 {
18             return 0
19         }
20         i = s.index(after: i)
21     }
22     return count
23     }
24 }

16ms

 1 class Solution {
 2     func numDecodings(_ s: String) -> Int {
 3         guard s.count > 0 else {
 4             return 0
 5         }
 6         
 7         let digits = Array(s).map { Int(String($0))! }
 8         var dp = Array(repeating: 0, count: digits.count + 1)
 9         dp[0] = 1
10         dp[1] = digits[0] == 0 ? 0 : 1
11         for i in stride(from: 2, through: digits.count, by: 1) {
12             dp[i] += (digits[i - 1] > 0 ? dp[i - 1] : 0)
13             let num = digits[i - 2] * 10 + digits[i - 1]
14             dp[i] += ((num >= 10 && num <= 26) ? dp[i - 2] : 0)
15         }
16         
17         return dp[digits.count]
18     }
19 }

20ms

 1 class Solution {
 2     func numDecodings(_ s: String) -> Int {
 3         guard !s.isEmpty && s.first! != "0" else {
 4             return 0
 5         }
 6         
 7         if s.count == 1 {
 8             return 1
 9         }
10         
11         var sum: [Int] = [1]
12         
13         let first = s[s.startIndex]
14         let second = s[s.index(after: s.startIndex)]
15         if second == "0" && first >= "3" {
16             return 0
17         }
18         
19         let str = String(first) + String(second)
20         if str == "10" || str == "20" || str > "26" {
21             sum.append(1)
22         }
23         else {
24             sum.append(2)
25         }
26         
27         for i in 2..<s.count {
28             let index = String.Index(encodedOffset: i)
29             let lastIndex = String.Index(encodedOffset: i-1)
30             if s[index] == "0" && (s[lastIndex] == "0" || s[lastIndex] >= "3") {
31                 return 0
32             }
33             
34             if s[index] == "0" {
35                 sum.append(sum[i-2])
36             }
37             else {
38                 if s[lastIndex] == "1" || (s[lastIndex] == "2" && s[index] <= "6") {
39                     sum.append(sum[i-1] + sum[i-2])
40                 }
41                 else {
42                     sum.append(sum[i-1])
43                 }
44             }
45         }
46         
47         return sum.last!
48     }
49 }

28ms

 1 class Solution {
 2     func numDecodings(_ s: String) -> Int {
 3         if s.count == 0 {
 4             return 0
 5         }
 6 
 7         let n = s.count
 8         var s = s
 9         var cache = [Int](repeating: -1, count: n + 1)
10         cache[n] = 1
11         return num(0, &s, &cache)
12     }
13 
14     fileprivate func num(_ i: Int, _ s: inout String, _ cache: inout [Int]) -> Int {
15         if cache[i] > -1 {
16             return cache[i]
17         }
18         if s[i] == "0" {
19             cache[i] = 0
20             return 0
21         }
22         var res = num(i + 1, &s, &cache)
23         if i < s.count - 1 && (s[i] == "1" || s[i] == "2" && s[i + 1] < "7") {
24             res += num(i + 2, &s, &cache)
25         }
26         cache[i] = res
27 
28         return res
29     }
30 }
31 
32 extension String {
33     subscript (i: Int) -> Character {
34         return self[index(startIndex, offsetBy: i)]
35     }
36 }

32ms

 1 class Solution {
 2     
 3     func numDecodings(_ s: String) -> Int {
 4         
 5         guard s.count > 0 else {
 6             
 7             return 0
 8         }
 9         
10         guard s.count > 1 else {
11             
12             if s[0] == "0" {
13 
14                return 0 
15             }
16             
17             return 1
18         }
19         var dp = Array(repeating: 0, count: s.count + 1)
20         dp[s.count] = 1
21         dp[s.count - 1] = s[s.count - 1] == "0" ? 0 : 1
22         
23         for i in (0...s.count - 2).reversed() {
24             
25             if s[i] == "0" {
26 
27                 continue
28             }
29             
30             dp[i] = Int(s[i..<i+2])! <= 26 ? dp[i + 1] + dp[i + 2] : dp[i + 1]
31         }
32         
33         return dp[0]
34     }
35 }
36 
37 extension String {
38   
39     subscript (i: Int) -> Character {
40     
41         return self[index(startIndex, offsetBy: i)]
42     }
43     
44     subscript (bounds: CountableRange<Int>) -> String {
45 
46         let start = index(startIndex, offsetBy: bounds.lowerBound)
47         let end = index(startIndex, offsetBy: bounds.upperBound)
48         return String(self[start ..< end])
49     }
50 }

36ms

 1 class Solution {
 2     func numDecodings(_ s: String) -> Int {
 3         guard s.count > 0 else {
 4             return 0
 5         }
 6         var result = [Int](repeating: 1, count: s.count + 1)
 7         result[s.count - 1] = (Int(String(s[s.count - 1])) ?? 0) > 0 ? 1 : 0
 8         for index in stride(from: s.count - 2, through: 0, by: -1) {
 9             if ((Int(String(s[index])) ?? 0) == 0) {
10                 result[index] = 0
11             } else if ((Int(String(s[index...index + 1])) ?? 0) > 26) {
12                 result[index] = result[index + 1]
13             } else {
14                 result[index] = result[index + 1] + result[index + 2]
15             }
16         }
17         return result[0]
18     }
19 }
20 
21 extension String {
22     subscript (i: Int) -> Character {
23         return self[index(startIndex, offsetBy: i)]
24     }
25     subscript (bounds: CountableRange<Int>) -> Substring {
26         let start = index(startIndex, offsetBy: bounds.lowerBound)
27         let end = index(startIndex, offsetBy: bounds.upperBound)
28         return self[start ..< end]
29     }
30     subscript (bounds: CountableClosedRange<Int>) -> Substring {
31         let start = index(startIndex, offsetBy: bounds.lowerBound)
32         let end = index(startIndex, offsetBy: bounds.upperBound)
33         return self[start ... end]
34     }
35     subscript (bounds: CountablePartialRangeFrom<Int>) -> Substring {
36         let start = index(startIndex, offsetBy: bounds.lowerBound)
37         let end = index(endIndex, offsetBy: -1)
38         return self[start ... end]
39     }
40     subscript (bounds: PartialRangeThrough<Int>) -> Substring {
41         let end = index(startIndex, offsetBy: bounds.upperBound)
42         return self[startIndex ... end]
43     }
44     subscript (bounds: PartialRangeUpTo<Int>) -> Substring {
45         let end = index(startIndex, offsetBy: bounds.upperBound)
46         return self[startIndex ..< end]
47     }
48 }
49 
50 extension Substring {
51     subscript (i: Int) -> Character {
52         return self[index(startIndex, offsetBy: i)]
53     }
54     subscript (bounds: CountableRange<Int>) -> Substring {
55         let start = index(startIndex, offsetBy: bounds.lowerBound)
56         let end = index(startIndex, offsetBy: bounds.upperBound)
57         return self[start ..< end]
58     }
59     subscript (bounds: CountableClosedRange<Int>) -> Substring {
60         let start = index(startIndex, offsetBy: bounds.lowerBound)
61         let end = index(startIndex, offsetBy: bounds.upperBound)
62         return self[start ... end]
63     }
64     subscript (bounds: CountablePartialRangeFrom<Int>) -> Substring {
65         let start = index(startIndex, offsetBy: bounds.lowerBound)
66         let end = index(endIndex, offsetBy: -1)
67         return self[start ... end]
68     }
69     subscript (bounds: PartialRangeThrough<Int>) -> Substring {
70         let end = index(startIndex, offsetBy: bounds.upperBound)
71         return self[startIndex ... end]
72     }
73     subscript (bounds: PartialRangeUpTo<Int>) -> Substring {
74         let end = index(startIndex, offsetBy: bounds.upperBound)
75         return self[startIndex ..< end]
76     }
77 }

48ms

 1 class Solution {
 2     
 3     func decodeHelperDynamic(str: String, n: Int, memo: inout [Int]) -> Int {
 4     if n == 0 { return 1 }
 5     
 6     let s = str.count - n
 7     let sIndex = str.index(str.startIndex, offsetBy: s)
 8     if str[sIndex] == "0" { return 0 }
 9     
10     if memo[n] != -1 {
11         return memo[n]
12     }
13     
14     var result = decodeHelperDynamic(str: str, n: n - 1, memo: &memo)
15     if n >= 2 {
16         let startIndex = str.index(str.startIndex, offsetBy: s)
17         let finishIndex = str.index(str.startIndex, offsetBy: s + 2)
18         let subStr = str[startIndex..<finishIndex]
19         if let subInt = Int(subStr), subInt <= 26 {
20             result += decodeHelperDynamic(str: str, n: n - 2, memo: &memo)
21         }
22     }
23     memo[n] = result
24     return result
25 }
26 
27     func numDecodings(_ s: String) -> Int {
28         
29     let n = s.count
30     var memo = Array(repeating: -1, count: n + 1)
31     return decodeHelperDynamic(str: s, n: n, memo: &memo)
32         
33     }
34 }