Menu Close

Decode Ways Problems

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

Lời giải

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= '1' && s[i] <= '9'){
                ways += dp[i+1];
            }
            dp[i] = ways;
            i--;
        }
        return dp[0];
    }

Leave a Reply

Your email address will not be published. Required fields are marked *