Decode Ways (LeetCode 91) | Full Solution with visuals | Recursion to Dynamic Programming

Join this channel to get access to perks: / @nikoo28
Actual problem on LeetCode: leetcode.com/problems/decode-...
Chapters:
00:00 - Intro
00:43 - Problem Statement
05:00 - Recursive Solution with Decision Tree
10:39 - How to optimize and memoize
14:18 - Dynamic Programming
18:48 - Dry-run of Code
21:50 - Final Thoughts
📚 Links to topics I talk about in the video:
Brute Force Method: • Brute Force algorithms...
Recursion: • Recursion paradigms wi...
Dynamic Programming: • Dynamic Programming ea...
Climbing Stairs: • Climbing Stairs (LeetC...
Playlist on Dynamic Programming: • Dynamic Programming
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/3sJm8Wl
Favorite book to understand algorithms: amzn.to/4848xJH
Favorite book for data structures: amzn.to/3P96YBv
Get started for interview preparation: amzn.to/44Nn5du
🔗 To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
🎥 My Recording Gear:
Recording Light: amzn.to/3PdsViT
Microphone: amzn.to/3Exv83x
Recording Camera: amzn.to/3PwyN8e
Tablet to sketch and draw: amzn.to/3ZdKVy7
Sketching Tool: amzn.to/45XJEgY
Laptop to edit videos: amzn.to/460ofDu
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview

[@lamebert]

This is insane, i wasnt able to understand the neetcode solution, but i am able to understand this! Thanks

[@chandan07talreja]

Thanks for detailed explanation Nikhil. Really appreciate it.

[@Md_sadiq_Md]

Pushing the algorithm

[@floatingfortress721]

Thank you very much! You were able to simplify the problem for me and now I actually understand it

[@akshitjain2906]

legend

[@rudreshcm4172]

Hey nikhil, first of all thanks for your top notch leetcode video solutions. Can you please make one video that should provide roadmap specific to your uploaded playlists/videos. This really make difference and increase watch count.

[@nikoo28]

I have created some playlists, but yes...can define a better roadmap too. Will work on it. Thanks. :)

[@prashanthshetty8337]

Thank you very much for the detailed explanation. instead of dp[], we could use 2 place holders to keep track of previous sum right? all we care is i-1 and i-2 can be tracked as prev1 and prev2.

[@nikoo28]

That's a great idea! Will save you space.

[@Khadyot_Takale]

IF C++ CODE IS FAILING this is because substring function it shoule be like s.substr(i-1,1) and s.substr(i-2,2) the second parameter is the length of the string.
this should work
class Solution {
public:
int numDecodings(string s) {
int n = s.length();

vector dp(n + 1);
dp[0] = 1;
dp[1] = s[0] == '0' ? 0: 1;
for(int i = 2; i < n + 1; i++){
int d1 = stoi(s.substr(i-1,1));
int d2 = stoi(s.substr(i-2,2));
if(d1 >= 1){
dp[i] += dp[i-1];
}
if(d2 >= 10 && d2

[@tamils12345]

class Solution {
public:
int numDecodings(string s) {
vector dp(s.length() + 1);
dp[0] = 1;
dp[1] = (s.at(0) == '0')?0:1;
for(int i = 2; i= 1) {
dp[i] += dp[i-1];
}
if (double_digit >= 10 && double_digit

[@jst8922]

The issue stems from how you're extracting single and double-digit numbers using stoi and substr.
Here's a breakdown of the problem and the solution:
Problem:
Incorrect Substring Extraction: The substr(i-1, i) in stoi(s.substr(i-1, i)) doesn't extract a single digit. Instead, it extracts a substring from index i-1 up to (but not including) index i. This means you're always getting a two-character substring (except for the last iteration).
Unnecessary stoi: You don't need stoi to check if a single digit is between 1 and 9. A simple character comparison is more efficient.
tested & working on lc
class Solution {
public:
int numDecodings(string s) {
int n = s.length();
vector dp(n + 1);
dp[0] = 1; // Empty substring has one way to decode
dp[1] = (s[0] == '0') ? 0 : 1; // First digit can't be '0'
for (int i = 2; i = 1 && single_digit = 10 && double_digit

[@tamils12345]

@@jst8922 thanks man.

[@GmHighlight12]

What if String length only 2 this code will failed to execute

[@debashismahapatra5961]

I tested with string length as 2. It works. Can you share specific examples that failed for you ?

[@GmHighlight12]

Try to run this code on leetcode all test cases won’t pass

[@debashismahapatra5961]

@@GmHighlight12 It does pass all test cases.
I tore the code to determine the breakage point. Looks like you may be hinting at the test case "10". Is that the one ?

[@sriyanandakuchimanchi4042]

no it will work
instead of writing dp[1] like that.,,add this check
if(s.charAt(0)=='0'||s.length==0||s==null){
return 0;
}