Decode Ways

문제

https://leetcode.com/problems/decode-ways/description/

입력

1 <= s.length <= 100 // 숫자로 쓰여진 문자열

결과

ans: Int = 주어진 s를 알파벳으로 디코딩할 수 있는 경우의 수

해석

동전 문제와 비슷하게 해석할 수 있다.

여기서 제약조건은 알파벳은 1 ~ 26까지 대응되며,  01 , 02 같은 형태는 없는 형태이다. 

코드

extension String {
    subscript(_ index: Int) -> String {
      return String(self[self.index(self.startIndex, offsetBy: index)])
    }
}
class Solution {
    func numDecodings(_ s: String) -> Int {
        guard !s.isEmpty else { return 0 }
        let n = s.count
        var cache: [Int] = [Int](repeating: -1, count:n+1)
        cache[n] = 1

      for i in stride(from: n-1, through: 0, by: -1) {
        if s[i] == "0" {
          cache[i] = 0
        } else {
          cache[i] = cache[i+1]
          if i < n-1 && ( s[i] == "1" || ( s[i] == "2" && s[i+1] < "7" )) {
            cache[i] += cache[i+2]
          }
        } 
      }
      return cache[0]
    }
}