daily pastebin goal
66%
SHARE
TWEET

639. Decode Ways II

HXXXXJ Feb 18th, 2019 (edited) 83 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. func numDecodings(_ s: String) -> Int {
  2.         if s.isEmpty {
  3.             return 0
  4.         }
  5.         let nums = Array(s.utf16).map { Int($0) - 48}
  6.         let star = Int(Array("*".utf16)[0]) - 48
  7.        
  8.         var dp = [Int](repeating: 0, count: nums.count + 1)
  9.        
  10.         if nums[0] == 0 {
  11.             // 012 return 0 result
  12.             return 0
  13.         }
  14.        
  15.         // initialize
  16.         dp[0] = 1
  17.         dp[1] = nums[0] == star ? 9 : 1
  18.        
  19.         // corner case "*" or "4"
  20.         if nums.count == 1 {
  21.             return dp[1]
  22.         }
  23.        
  24.         for i in 2...nums.count {
  25.             // first consider single digit at nums[i - 1]
  26.             if nums[i - 1] > 0 && nums[i - 1] < 10 {
  27.                 // case normal number: "123"
  28.                 dp[i] += dp[i - 1]
  29.             } else if nums[i - 1] == star {
  30.                 // * case "12*"
  31.                 dp[i] += dp[i - 1] * 9
  32.             }
  33.            
  34.             // second consider two digits at nums[i - 2], nums[i - 1]
  35.             if nums[i - 1] != star && nums[i - 2] != star {
  36.                 //122 check num 10-26 or not
  37.                 let num = nums[i - 2] * 10 + nums[i - 1]
  38.                 if num >= 10 && num <= 26 {
  39.                     dp[i] += dp[i - 2]
  40.                 }
  41.             } else if nums[i - 1] == star && nums[i - 2] == star {
  42.                 // 1**:  10-26 so 15
  43.                 dp[i] += dp[i - 2] * (9 + 6)
  44.             } else if nums[i - 2] != star {
  45.                 // 1* and 2* two cases
  46.                 if nums[i - 2] == 2 {
  47.                     dp[i] += dp[i - 2] * 6
  48.                 } else if nums[i - 2] == 1 {
  49.                     dp[i] += dp[i - 2] * 9
  50.                 }
  51.             } else {
  52.                 // *X two case X == 0-6 (10, 20, 11, 21, ..., 16, 26) and X == 7-9 (17, 18, 19)
  53.                 if nums[i - 1] < 7 {
  54.                     dp[i] += dp[i - 2] * 2
  55.                 } else {
  56.                     dp[i] += dp[i - 2]
  57.                 }
  58.             }
  59.            
  60.             // I think as swift is dynamic, we don't need to worry about this, but the testcase answers are %1000000007
  61.             // case like "*************" would overflow Int32 if we dont mod 1000000007 in order to pass the testcase result            
  62.             dp[i] %= 1000000007
  63.         }
  64.         return dp[nums.count]
  65.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top