[LeetCode] Decode Ways

문제

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

 

Approach

Bottom-up DP로 풀었다.

memo배열을 만들고 string의 i번째 문자에서 부터 읽을 때 decode할 수 있는 경우의 수를 memo[i]에 저장한다.

string의 길이가 n일때 memo의 크기는 n+1로 하고 memo[n]은 1로 초기화

이후 string을 뒤에서 부터 읽으며 memo를 업데이트 한다.

2가지로 decode될 수 있는 경우 (string[i]가 1일때와 string[i]가 2이고 string[i+1]이 0-6일때)는

memo[i] = memo[i+1] + memo[i+2]를 해 줌으로써 대응하고

그 외의 경우는 memo[i] = memo[i+1]로 한다.

string[i]가 0이면 decode 할 수 없으므로 0으로 업데이트 한다.

최종적으로 memo[0]이 답이 된다.

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_DecodeWays.cpp

chi3236/algorithm