91. Decode Ways

📝 Problem Details

• Title: 91. Decode Ways
• Link: https://leetcode.com/problems/decode-ways/
• Difficulty: Medium
• Tags/Categories: Dynamic-Programming

💭What Were My Initial Thoughts?

- "return the number of ways" indicates an enumeration backtracking problem
- a DFS backtracking approach seems appropriate to find all possible ways to decode a string of numbers
- can we optimize the backtracking algorithm with memoization if there is a subproblem we can identify?
	- yes, if we encounter the same 1 or 2 digits again, we should already know how many ways we can decode them (we can cache it)

-----------------------------------

- the problem asks for the number of ways to decode a string where:
	- a -> 1, ... z -> 26
	- we must determine the number of valid ways to split the string into these mappings
- the phrase "number of ways" suggests enumeration which hints at dynamic programming if there is the presence of an overlapping subproblem
- initially considered DFS with memoization (top-down) , but realised we can also solve it iteratively using bottom-up dynamic programming

💡 Explanation of Solution

1. define state:
	- let dp[i] be the number of ways to decode the substring s[0:1]
	- goal is to compute dp[n] where n = s.size()

2. base cases:
	- dp[0] = 1: an empty string has exactly one way to decode (doing nothing)
	- dp[1] = 1 if s[0] != '0', otherwise 0
		- if s[0] = '0' then decoding is impossible

3. dp transition
	- for every position i, consider:
		- single digit decode (using s[i-1])
		- two digit decode (using s[i-2] s[i-1])

⌛ Complexity Analysis

Time Complexity: O(n)
Time Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    int numDecodings(string s) {
        // edge case: starts with '0'
        if(s.empty() || s[0] == '0') return 0;
    
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1; // base case : empty string has one way to decode
        dp[1] = s[0] != '0' ? 1 : 0; // single character case
 
        for(int i=2; i <= n; i++) {
            //check for single digit decode
            if(s[i-1] != '0') dp[i] += dp[i-1];
 
            // check two digit decode
            int twoDigit = stoi(s.substr(i-2, 2));
            if(10 <= twoDigit && twoDigit <= 26) dp[i] += dp[i-2];
        }
 
        return dp[n];
    }
};