Decode Ways - Leetcode 91 - Python
Don't forget to check the following links:
Notes and theory:
https://github.com/djeada/Leetcode-So...
Refined solution:
https://github.com/djeada/Leetcode-So...
My blog:
https://adamdjellouli.com/
We maintain four main variables: `s`, the input digit string to decode; `ways_two_back`, which corresponds to the number of ways to decode the prefix ending two positions before the current index; `ways_one_back`, which corresponds to the number of ways to decode the prefix ending at the previous index; and `ways_current`, which will hold the number of ways to decode the prefix ending at the current index. Additionally, for each character we consider, we compute `two_digit` as the integer value of the substring formed by the current character and its predecessor. By keeping only these three DP values instead of a full array, we achieve constant space usage.
First, we handle invalid or trivial cases: if the string is empty or its first character is zero, no decodings exist and we return zero. Otherwise, we set `ways_two_back` and `ways_one_back` both to one, reflecting that an empty prefix has one way to decode and a single nonzero digit also has one valid decoding. Then we loop through each index from one up to the end of the string. At each step, we reset `ways_current` to zero. If the current digit is nonzero, it can stand alone, so we add `ways_one_back` to `ways_current`. Next, we parse the two-digit number formed by the previous and current digits; if that value lies between ten and twenty-six inclusive, we add `ways_two_back`. After these checks, we slide the window by assigning `ways_two_back` to the old `ways_one_back` and `ways_one_back` to `ways_current`. If `ways_one_back` ever becomes zero, it means no valid decodings extend beyond this point, so we return zero immediately.
When the loop finishes, `ways_one_back` holds the total number of ways to decode the entire string, and we return that. Because we process each character exactly once with only constant-time checks and updates, the time complexity is linear in the length of the string. Since we only ever use three integer variables (plus a temporary for the two-digit parse) and no additional arrays or data structures, the space complexity remains constant.
Sur cette page du site, vous pouvez voir la vidéo en ligne Decode Ways - Leetcode 91 - Python durée heure minute seconde en bonne qualité , qui a été Téléchargé par l'utilisateur Adam Djellouli 01 janvier 1970, Partagez le lien avec vos amis et connaissances, sur youtube cette vidéo a déjà été regardée 63 fois et il a aimé 0 téléspectateurs. Bon visionnage!
