• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode639.解码方法2|DecodeWaysII

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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: 9
Explanation: 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:

  1. The length of the input string will fit in range [1, 105].
  2. 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", "B", "C", "D", "E", "F", "G", "H", "I".

示例 2 :

输入: "1*"
输出: 9 + 9 = 18(翻译者标注:这里1*可以分解为1,* 或者当做1*来处理,所以结果是9+9=18)

说明 :

  1. 输入的字符串长度范围是 [1, 105]。
  2. 输入的字符串只会包含字符 '*' 和 数字'0' - '9'。

Runtime: 224 ms
Memory Usage: 19.9 MB
 1 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 * e2
13                 e1 = e0
14                 e2 = e0
15             }
16             else
17             {
18                 f0 = e1
19                 if c > "0"
20                 {
21                     f0 += e0
22                 }                
23                 if c <= "6"
24                 {
25                     f0 += e2
26                 }                
27                 e1 = c == "1" ? e0 : 0                
28                 e2 = c == "2" ? e0 : 0
29             }
30             e0 = f0 % M
31         }
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 <= 26
102                         {                            
103                             dynamicResults[ startIndex ] = 
104                                 ( 
105                                     dynamicResults[ startIndex ] 
106                                     + countDecodingsR( startIndex + 2 )
107                                 ) % mod
108                         }                         
109                         else
110                         {
111                             break
112                         }                        
113                     }
114                 }
115                 else
116                 {                    
117                     let value: Int = values[ startIndex ] * 10 + values[ startIndex + 1 ]                       
118                     if value <= 26
119                     {                        
120                         dynamicResults[ startIndex ] = 
121                             ( 
122                                 dynamicResults[ startIndex ] 
123                                 + countDecodingsR( startIndex + 2 )
124                             ) % mod
125                     }
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 >= 0
136             {
137                 if values[ currentIndex ] == 0
138                 {
139                     dynamicResults[ currentIndex ] = 0
140                     currentIndex -= 1                    
141                     continue
142                 }
143                 dynamicResults[ currentIndex ] = 0
144                 if values[ currentIndex ] == -1
145                 {
146                     dynamicResults[ currentIndex ] = 
147                         ( 
148                             dynamicResults[ currentIndex ] 
149                             + ( 9 * dynamicResults[ currentIndex + 1 ] ) % mod 
150                         ) % mod
151                     if values[ currentIndex + 1 ] == -1
152                     {
153                         dynamicResults[ currentIndex ] = 
154                             ( 
155                                 dynamicResults[ currentIndex ] 
156                                 + ( 15 * dynamicResults[ currentIndex + 2 ] ) % mod 
157                             ) % mod 
158                     }
159                     else
160                     {
161                         if 10 + values[ currentIndex + 1 ] <= 26
162                         {
163                             dynamicResults[ currentIndex ] = 
164                                 ( 
165                                     dynamicResults[ currentIndex ] 
166                                     + dynamicResults[ currentIndex + 2 ]
167                                 ) % mod                      
168                         }
169 
170                         if 20 + values[ currentIndex + 1 ] <= 26
171                         {
172                             dynamicResults[ currentIndex ] = 
173                                 ( 
174                                     dynamicResults[ currentIndex ] 
175                                     + dynamicResults[ currentIndex + 2 ]
176                                 ) % mod
177                         }
178                     }
179                 }
180                 else
181                 {
182                     dynamicResults[ currentIndex ] = 
183                         ( 
184                             dynamicResults[ currentIndex ] 
185                             + dynamicResults[ currentIndex + 1 ]
186                         ) % mod
187                     if values[ currentIndex + 1 ] == -1
188                     {
189                         var value: Int = values[ currentIndex ] * 10
190                         for digit in ( 1 ... 9 )
191                         {
192                             if value + digit <= 26
193                             {
194                                 dynamicResults[ currentIndex ] = 
195                                     ( 
196                                         dynamicResults[ currentIndex ] 
197                                         + dynamicResults[ currentIndex + 2 ]
198                                     ) % mod
199                             }                         
200                             else
201                             {
202                                 break
203                             }
204                         }         
205                     }
206                     else
207                     {
208                         let value: Int = values[ currentIndex ] * 10 + values[ currentIndex + 1 ]   
209                         if value <= 26
210                         {
211                             dynamicResults[ currentIndex ] = 
212                                 ( 
213                                     dynamicResults[ currentIndex ] 
214                                     + dynamicResults[ currentIndex + 2 ]
215                                 ) % mod
216                         }                      
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{ "\($0)" }
 5         var dp = Array(repeating: 0, count: s.count)
 6         dp[0] = s[0] == "*" ? 9 : s[0] == "0" ? 0 : 1
 7         for i in 1..<s.count {
 8             var r = (i > 1) ? dp[i-2] : 1
 9             if s[i] == "*" {
10                 dp[i] = dp[i] &+ dp[i-1] * 9 
11                 if s[i-1] == "1" { dp[i] = dp[i] &+ r * 9  }
12                 if s[i-1] == "2" { dp[i] = dp[i] &+ r * 6 }
13                 if s[i-1] == "*" { dp[i] = dp[i] &+ r * 15 }
14             } else if s[i] == "0" {
15                 r = (i > 1) ? dp[i-2] : 1
16                 if s[i-1] == "1" || s[i-1] == "2" { dp[i] += r * 1 }
17                 if s[i-1] == "*" { dp[i] += r * 2 }
18             } else {
19                 dp[i] = dp[i] &+ dp[i-1] 
20                 if s[i-1] == "1" || (s[i-1] == "2" && Int(s[i])! < 7)  { dp[i] = dp[i] &+ ((i > 1) ? dp[i-2] : 1) }
21                 if s[i-1] == "*" && Int(s[i])! < 7 { dp[i] = dp[i] &+ r * 2 }
22                 if s[i-1] == "*" && Int(s[i])! >= 7 { dp[i] = dp[i] &+ r * 1 }
23             }
24             dp[i] %= 1000000007
25         }
26         return dp.last ?? 0
27     }
28 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift开源项目练习应用发布时间:2022-07-13
下一篇:
[Swift]LeetCode899.有序队列|OrderlyQueue发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap