# Decode Ways Problems

blackntt

# Problem

Cho một chuỗi số N kí tự. Tìm số cách có thể giải mã chuỗi số đó. Biết bảng mã hoá như sau: A -> 1, B -> 2, …, Z -> 26.

Ví dụ “226” – kết quả là 3 vì (2|26, 22|6, 2|2|6) – 3 cách có thể giải mã.

# Solution

# Media

# Dynamic programming

Độ phức tạp thời gian: O(n)
Độ phức tạp không gian: O(n)

int numDecodings(string s) {
        vector< int > dp(s.length()+1,0);
        dp[s.length()]=1;
        if(s[s.length()-1] >= '1'&&s[s.length()-1] <= '9'){
                dp[s.length()-1]=1;
        }
        int i=s.length()-2;
        while(i>=0){
            int ways = 0;
            if(i+1<s.length() &#038;&#038; (s[i] == '1'||(s[i] == '2' &#038;&#038; s[i+1] <= '6'))){
                ways=dp[i+2];
            }
            if(s[i] >= '1' && s[i] <= '9'){
                ways += dp[i+1];
            }
            dp[i] = ways;
            i--;
        }
        return dp[0];
    }