![[Swift]LeetCode639. 解码方法 2 | Decode Ways II,第1张](/aiimages/%5BSwift%5DLeetCode639.+%E8%A7%A3%E7%A0%81%E6%96%B9%E6%B3%95+2+%7C+Decode+Ways+II.png "[Swift]LeetCode639. 解码方法 2 | Decode Ways II,第1张")
A message containing letters from A-Z is being encoded to numbers using the following mapPing way:
‘A‘ -> 1‘B‘ -> 2...‘Z‘ -> 26
Beyond that,Now the encoded string can also contain the character ‘*‘,which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character ‘*‘,return the total number of ways to decode it.
Also,since the answer may be very large,you should return the output mod 109 + 7.
Example 1:
input: "*"Output: 9Explanation: The encoded message can be decoded to the string: "A","B","C","D","E","F","G","H","I".
Example 2:
input: "1*"Output: 9 + 9 = 18
Note:
The length of the input string will fit in range [1,105]. The input string will only contain the character ‘*‘ and digits ‘0‘ - ‘9‘.一条包含字母 A-Z 的消息通过以下的方式进行了编码：
‘A‘ -> 1‘B‘ -> 2...‘Z‘ -> 26
除了上述的条件以外，现在加密字符串可以包含字符 ‘*‘了，字符‘*‘可以被当做1到9当中的任意一个数字。
给定一条包含数字和字符‘*‘的加密信息，请确定解码方法的总数。
同时，由于结果值可能会相当的大，所以你应当对109 + 7取模。（翻译者标注：此处取模主要是为了防止溢出）
示例 1 :
输入: "*"输出: 9解释: 加密的信息可以被解密为: "A","I".
示例 2 :
输入: "1*"输出: 9 + 9 = 18（翻译者标注：这里1*可以分解为1,* 或者当做1*来处理，所以结果是9+9=18）
说明 :
输入的字符串长度范围是 [1,105]。 输入的字符串只会包含字符 ‘*‘ 和 数字‘0‘ - ‘9‘。 Runtime: 224 ms Memory Usage: 19.9 MB1 class Solution { 2 func numDeCodings(_ s: String) -> Int { 3 var e0:Int64 = 1 4 var e1:Int64 = 0 5 var e2:Int64 = 0 6 var f0:Int64 = 0 7 var M:Int64 = Int64(1e9 + 7) 8 for c in s.characters 9 {10 if c == "*"11 {12 f0 = 9 * e0 + 9 * e1 + 6 * e213 e1 = e014 e2 = e015 }16 else17 {18 f0 = e119 if c > "0"20 {21 f0 += e022 } 23 if c <= "6"24 {25 f0 += e226 } 27 e1 = c == "1" ? e0 : 0 28 e2 = c == "2" ? e0 : 029 }30 e0 = f0 % M31 }32 return Int(e0)33 }34 }
340ms
1 /* Solution Space */ 2 3 class Solution 4 { 5 /* Algorithm */ 6 func numDeCodings( _ string1: String ) -> Int 7 { 8 let allChar: UInt8 = "*".utf8.first! 9 let zeroChar: UInt8 = "0".utf8.first! 10 let values: [ Int ] = string1.utf8.map( 11 { 12 if $0 == allChar 13 { 14 return -1 15 } 16 else 17 { 18 return Int( $0 - zeroChar ) 19 } 20 } 21 ) 22 let mod: Int = 1000000007 23 24 /* Dynamic Results */ 25 var dynamicResults: [ Int ] = [ Int ].init( repeating: -1,count: ( values.count + 1 ) ) 26 dynamicResults[ values.count ] = 1 27 if values[ values.count - 1 ] == 0 28 { 29 dynamicResults[ values.count - 1 ] = 0 30 } 31 else if values[ values.count - 1 ] == -1 32 { 33 dynamicResults[ values.count - 1 ] = 9 34 } 35 else 36 { 37 dynamicResults[ values.count - 1 ] = 1 38 } 39 40 /* Counting Function - Recursive */ 41 func countDeCodingsR( _ startIndex: Int ) -> Int 42 { 43 if dynamicResults[ startIndex ] != -1 44 { 45 return dynamicResults[ startIndex ] 46 } 47 if values[ startIndex ] == 0 48 { 49 dynamicResults[ startIndex ] = 0 50 return dynamicResults[ startIndex ] 51 } 52 dynamicResults[ startIndex ] = 0 53 if values[ startIndex ] == -1 54 { 55 dynamicResults[ startIndex ] = 56 ( 57 dynamicResults[ startIndex ] 58 + ( 9 * countDeCodingsR( startIndex + 1 ) ) % mod 59 ) % mod 60 if values[ startIndex + 1 ] == -1 61 { 62 dynamicResults[ startIndex ] = 63 ( 64 dynamicResults[ startIndex ] 65 + ( 15 * countDeCodingsR( startIndex + 2 ) ) % mod 66 ) % mod 67 } 68 else 69 { 70 if 10 + values[ startIndex + 1 ] <= 26 71 { 72 dynamicResults[ startIndex ] = 73 ( 74 dynamicResults[ startIndex ] 75 + countDeCodingsR( startIndex + 2 ) 76 ) % mod 77 } 78 if 20 + values[ startIndex + 1 ] <= 26 79 { 80 81 dynamicResults[ startIndex ] = 82 ( 83 dynamicResults[ startIndex ] 84 + countDeCodingsR( startIndex + 2 ) 85 ) % mod 86 } 87 } 88 } 89 else 90 { 91 dynamicResults[ startIndex ] = 92 ( 93 dynamicResults[ startIndex ] 94 + countDeCodingsR( startIndex + 1 ) 95 ) % mod 96 if values[ startIndex + 1 ] == -1 97 { 98 var value: Int = values[ startIndex ] * 10 99 for digit in ( 1 ... 9 )100 { 101 if value + digit <= 26102 { 103 dynamicResults[ startIndex ] = 104 ( 105 dynamicResults[ startIndex ] 106 + countDeCodingsR( startIndex + 2 )107 ) % mod108 } 109 else110 {111 break112 } 113 }114 }115 else116 { 117 let value: Int = values[ startIndex ] * 10 + values[ startIndex + 1 ] 118 if value <= 26119 { 120 dynamicResults[ startIndex ] = 121 ( 122 dynamicResults[ startIndex ] 123 + countDeCodingsR( startIndex + 2 )124 ) % mod125 }126 }127 } 128 return dynamicResults[ startIndex ] 129 }130 131 /* Counting Function - Iterative */ 132 func countDeCodingsI()133 { 134 var currentIndex: Int = ( values.count - 2 ) 135 while currentIndex >= 0136 {137 if values[ currentIndex ] == 0138 {139 dynamicResults[ currentIndex ] = 0140 currentIndex -= 1 141 continue142 }143 dynamicResults[ currentIndex ] = 0144 if values[ currentIndex ] == -1145 {146 dynamicResults[ currentIndex ] = 147 ( 148 dynamicResults[ currentIndex ] 149 + ( 9 * dynamicResults[ currentIndex + 1 ] ) % mod 150 ) % mod151 if values[ currentIndex + 1 ] == -1152 {153 dynamicResults[ currentIndex ] = 154 ( 155 dynamicResults[ currentIndex ] 156 + ( 15 * dynamicResults[ currentIndex + 2 ] ) % mod 157 ) % mod 158 }159 else160 {161 if 10 + values[ currentIndex + 1 ] <= 26162 {163 dynamicResults[ currentIndex ] = 164 ( 165 dynamicResults[ currentIndex ] 166 + dynamicResults[ currentIndex + 2 ]167 ) % mod 168 }169 170 if 20 + values[ currentIndex + 1 ] <= 26171 {172 dynamicResults[ currentIndex ] = 173 ( 174 dynamicResults[ currentIndex ] 175 + dynamicResults[ currentIndex + 2 ]176 ) % mod177 }178 }179 }180 else181 {182 dynamicResults[ currentIndex ] = 183 ( 184 dynamicResults[ currentIndex ] 185 + dynamicResults[ currentIndex + 1 ]186 ) % mod187 if values[ currentIndex + 1 ] == -1188 {189 var value: Int = values[ currentIndex ] * 10190 for digit in ( 1 ... 9 )191 {192 if value + digit <= 26193 {194 dynamicResults[ currentIndex ] = 195 ( 196 dynamicResults[ currentIndex ] 197 + dynamicResults[ currentIndex + 2 ]198 ) % mod199 } 200 else201 {202 break203 }204 } 205 }206 else207 {208 let value: Int = values[ currentIndex ] * 10 + values[ currentIndex + 1 ] 209 if value <= 26210 {211 dynamicResults[ currentIndex ] = 212 ( 213 dynamicResults[ currentIndex ] 214 + dynamicResults[ currentIndex + 2 ]215 ) % mod216 } 217 } 218 } 219 currentIndex -= 1 220 } 221 } 222 countDeCodingsI() 223 return dynamicResults[ 0 ] 224 } 225 }
780ms
1 class Solution { 2 func numDeCodings(_ s: String) -> Int { 3 guard s.count > 0 else { return 0 } 4 let s = Array(s).map{ "\(") } 5var 0 dp = Array(repeating: ,count: s.count) 60 dp[0] = s["] == *"9 ? 0 : s["] == 0"0 ? 1 : 7for in i 1 s.count {..< 8var 1 r = (i > 2) ? dp[i-1] : 9if " s[i] == *" {101 dp[i] = dp[i] &+ dp[i-9] * 11 if 1 s[i-"] == 1"9 { dp[i] = dp[i] &+ r * }12if 1 s[i-"] == 2"6 { dp[i] = dp[i] &+ r * }13if 1 s[i-"] == *"15 { dp[i] = dp[i] &+ r * }14else } if " s[i] == 0" {151 r = (i > 2) ? dp[i-1] : 16if 1 s[i-"] == 1"1 || s[i-"] == 2"1 { dp[i] += r * }17if 1 s[i-"] == *"2 { dp[i] += r * }18else } {191 dp[i] = dp[i] &+ dp[i-] 20if 1 s[i-"] == 1"1 || (s[i-"] == 2"7 && Int(s[i])! < 1) { dp[i] = dp[i] &+ ((i > 2) ? dp[i-1] : ) }21if 1 s[i-"] == *"7 && Int(s[i])! < 2 { dp[i] = dp[i] &+ r * }22if 1 s[i-"] == *"7 && Int(s[i])! >= 1 { dp[i] = dp[i] &+ r * }23 } 241000000007 dp[i] %= 25 } 26return 0 dp.last ?? 27 } 28 }总结
以上是内存溢出为你收集整理的[Swift]LeetCode639. 解码方法 2 | Decode Ways II全部内容，希望文章能够帮你解决[Swift]LeetCode639. 解码方法 2 | Decode Ways II所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）