91. Decode Ways

A message containing letters from A-Z can be encoded into numbers using the following mapping:

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

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

  • "AAJF" with the grouping (1 1 10 6)
  • "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

 

Example 1:

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

Example 2:

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

Example 3:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

 

Constraints:

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zero(s).
class Solution {
public:
    
    bool helper(string s){
    return stoi(s)>=10 && stoi(s)<=26;
    }
    
    int numDecodings(string s) {
        if(s[0]=='0')return 0;
        vector<int> dp(s.length()+1,0);
        dp[0]=1;
        dp[1]=1;


        for (int i = 2; i <=s.length(); i++)
        {
            if(s[i-1]!='0')dp[i]=dp[i-1];
            if(helper(s.substr(i-2,2)))dp[i]+=dp[i-2];
        }
        return dp[s.length()];
    }
};
class Solution {
public:
// to check if the string is valid or not like 06 is not valid but 10 is valid
bool helper(string s){
return stoi(s)>=10 && stoi(s)<=26;
}
int numDecodings(string s) {
// if the first letter itself is 0 then no combination possible
if(s[0]=='0')return 0;
// making a dp string to store the previous result
vector<int> dp(s.length()+1,0);
// as every string of zero is possible
dp[0]=1;
// as every string of length 1 is possible in one way
dp[1]=1;
// will start from index 2 in dp and index 1 in string ( using i-1 )
for (int i = 2; i <=s.length(); i++)
{
// if s[i-1] is not 0 then possible way is same as of dp[i-1]
if(s[i-1]!='0')dp[i]=dp[i-1];
// if s[i-2]+s[i-1] is valid and is not like 06 or 09 or 03 or 29 of 40 then we need to add to the current ways
if(helper(s.substr(i-2,2)))dp[i]+=dp[i-2];
}
return dp[s.length()];
}
};
Made with ❤ by Raunit Verma Rate Us 5⭐ Here