[leetcode 91] 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.

The answer is guaranteed to fit in a 32-bit integer.

 

Example 1:

Input: s = "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "0" Output: 0 Explanation: There is no character that is mapped to a number starting with '0'. We cannot ignore a zero when we face it while decoding. So, each '0' should be part of "10" --> 'J' or "20" --> 'T'.

Example 4:

Input: s = "1" Output: 1

 

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

문제풀이:

난이도가 medium이었지만 조건 따지기가 너무 힘들었다.

DP를 사용하지만 점화식 세우기가 넘 까다롭다...

 

문자열이 "12"라면

DP[0] = 1, DP[0] = 2가 될 것이다.

1 -> DP[0]

1 2 / 12 -> DP[1]이 되는 것을 확인할 수 있다.

 

문자열이 "123"이라고 해보자

1

1 2 / 12

1 2 3/ 12 3/ 1 23

여기서 DP[2]=3을 자세히 살펴보면 DP[1]에서 3만 붙인 게 2개, 새로 만들어진 23을 추가한 1개로 총 3이다.

 

문자열이 "127"이라면

1 2 7 / 12 7 만 있을 것이다. 27은 26을 넘기때문에 새로운 문자열을 형성할 수 없다.

그렇다면 여기서 한가지 식을 쓸 수 있다.

 

현재 문자가 0이 아니라는 가정하에 s[i-1]과 s[i]로 만든 숫자가 >= 10 && <=26 이라면 

dp[i] = dp[i-1] + dp[i-2]가 된다. (i-2>=0 조건 필요!)

i==1이라면 dp[i] = dp[i-1] + 1이 될 것이다.

 

++저 조건을 없애고 싶다면 dp[0] =1로 두고 dp[1]부터 계산하면 된다.

 

이번엔 "107"을 따져보자

1

10

10 7

s[i-1]과 s[i]로 만든 숫자가 <10 이라면 새로운 숫자를 만들 수 없으므로 dp[i] = dp[i-1]이 된다.

 

s[i] =0일 땐 따로 따져줘야 한다.

 

~~~~0 일때 s[i-1] 0이 10이나 20인 경우와 s[i-1]0 이 범위를 벗어나는 두 가지 경우가 있다.

후자의 경우 더 이상 디코드가 불가능하기 때문에 return 0을 한다. ex) 3405 디코드 불가능

 

 전자의 경우 

"210" 이면

2

2 1/ 21

2 10 -> s[i-2]와 동일한 것을 확인할 수 있다.

 

dp[i] = dp[i-2] 이 때 i-2>=0

만약 i==1이라면 (예 "10") 그냥 1이다. 

 

class Solution {
public:
    int numDecodings(string s) {
        int len = s.length();
        
        vector<int> dp(len,0);
        dp[0] = (s[0] =='0')? 0: 1;
        
        for(int i=1; i<len; i++){
            
            int n1 = s[i-1]-'0';
            int n2 = s[i] - '0';
            
            int sum = n1 * 10 + n2;
            
           if(n2 == 0){
               
               if(sum ==10 || sum == 20){
                   dp[i] = (i-2>=0)? dp[i-2]:1;
               }else{
                   return 0;
               }
               
           }else {
               
               dp[i] = dp[i-1];

               if(sum >= 10 && sum <= 26){
                   dp[i] += (i-2>=0)? dp[i-2]:1;
               }
           }
           
        }
        return dp[len-1];
    }
};