[leetcode] 639. Decode Ways II

문제 : https://leetcode.com/problems/decode-ways-ii/

---

A ~ Z 문자가 1 ~ 26 숫자로 인코딩된다.(01, 02 는 1, 2와 다르다.)

숫자와 * 문자로 이루어진 문자열이 주어진다.

* 문자는 0을 제외한 1~9로 대체할 수 있다. 

입력 문자열을 디코딩하였을 때 만들 수 있는 문자열들의 경우의 수를 구해라.

---

백트래킹과 DP(memoization)을 이용해서 풀었다.

dp[ind] = 입력문자열[ind~]로 만들 수 있는 정답 경우의 수

ind 번째 문자를 탐색 중일 때, 해당 문자는 십의자리로 디코딩될수도 있고, 일의자리로 디코딩 될 수도 있다.

두 가지 경우의 수를 구한뒤 더해준다.

 

십의 자리로 디코딩될 수 있는 경우의 수를 먼저 알아보자.

만일 ind+1 번째 문자가 없는 경우는 십의자리를 만들 수 없다.

ind 번째 문자를 first, ind+1 번째 문자를 second 라 하자.

 

1) first, second 모두 '*' 인경우

11~19, 21~26 수들을 만들 수 있다. 총 경우의 수는 15.

2) first는 '*', second는 숫자(let, X)인 경우

second가 0인 경우 10, 20 총 2개를 만들 수 있다.

second가 6이하인 경우, 1X, 2X 총 2개를 만들 수 있다.

second가 7이상인 경우, 1X 총 1개를 만들 수 있다.

3) first는 숫자(let, X) second는 '*'인 경우

first가 0이거나 3 이상인 경우, 십의자리는 만들 수 없다.

first가 1인 경우, 11 ~ 19 총 9개를 만들 수 있다.

first가 2인 경우, 21 ~ 26 총 6개를 만들 수 있다.

4) first, second 모두 숫자인 경우

first가 0이면 십의자리는 만들 수 없다.

10*first + second가 26이하이면 십의자리를 1개 만들 수 있고 27이상이면 십의자리를 만들 수 없다.

 

위와 같은 방법들로 십의 자리를 만드는 경우의 수를 구했다면 ind, ind+1 번째 문자를 사용했으므로 dp[ind+2](입력문자열[ind+2 ~]로 만들 수 있는 경우의 수)를 곱해준다.

 

이번엔 일의 자리로 디코딩될 수 있는 경우의 수를 알아보자.

1) ind 번째 문자가 0이면 일의 자리로 만들 수 없다.

2) ind 번째 문자가 0이 아닌 숫자인 경우 일의자리 1개를 만들 수 있다.

3) ind 번째 문자가 * 인 경우 1~9, 총 9개의 일의자리를 만들 수 있다.

일의 자리 수를 구했다면, 이 경우의 수에 dp[ind+1](입력문자열[ind+1 ~]로 만들 수 있는 경우의 수)를 곱해준다.

 

dp[ind] = (ind, ind+1 문자로 만들 수 있는 십의자리 경우의 수 * dp[ind+2])
           + (ind 문자로 만들 수 있는 일의자리 경우의 수 * dp[ind+1])

위 알고리즘들로 점화식을 구하면 위와 같다.

설명에서는 10^9 + 7 모듈러 연산을 생략했는데 int 형 범위를 안넘게 적절히 모듈러 연산을 추가해줘야 한다.

 

시간, 공간 복잡도는 입력 문자열 길이를 N 이라 했을 때, O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/639.%20Decode%20Ways%20II.cpp