Leetcode: Decode Ways

Decode Ways

My Submissions

Total Accepted: 55365 Total Submissions: 330885 Difficulty: Medium

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Subscribe to see which companies asked this question

Hide Tags

 Dynamic Programming String

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DP:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

////////////////////////////////////

//CODES

class Solution {

 public:

        int numDecodings(string s) {

               //check input

               if (s.size() == 0)return 0;

               vector<int> dp;

               dp.assign(s.size() + 1, 0);

               dp[0] = 1;

               //first item dp[1]

               int first = s[0] - '0';

               if (first == 0)dp[0] = 0;

               else dp[1] = 1;

               for (int i = 1; i<s.size(); i++){

                      int cur = s[i] - '0', pre = s[i - 1] - '0';

                      if (cur == 0 || pre == 0){

                            if (cur == 0 && pre == 0 || cur == 0 && pre >= 3)return 0;

                            if (cur == 0)dp[i + 1] = dp[i - 1];

                            else dp[i + 1] = dp[i];

                      }

                      else if (pre * 10 + cur <= 26) dp[i + 1] = dp[i] + dp[i - 1];

                      else dp[i + 1] = dp[i];

               }

               return dp[s.size()];

        }

 };