Skip to content

Instantly share code, notes, and snippets.

@emskaplann
Last active September 29, 2020 15:43
Show Gist options
  • Save emskaplann/0f0307c99a4678c7333f2fc7f26bba77 to your computer and use it in GitHub Desktop.
Save emskaplann/0f0307c99a4678c7333f2fc7f26bba77 to your computer and use it in GitHub Desktop.
My own solution for a popular Recursion Problem which is named as Decode Ways.
// This is a popular question asked on interviews. The optimum solution is achieved by using recursion. Because it's kind of building a binary tree with possible moves.
// **DECODE WAYS**
// PROBLEM DESCRIPTION:
// A message containing letters from A-Z is being encoded to numbers using the following mapping:
// 'A' -> 1
// 'B' -> 2
// ...
// 'Z' -> 26
// Given a non-empty string containing only digits, determine the total number of ways to decode it.
// The answer is guaranteed to fit in a 32-bit integer.
// Example 1:
// Input: s = "12"
// Output: 2
// Explanation: It could be decoded as "AB" (1 2) or "L" (12).
// Example 2:
// Input: s = "226"
// Output: 3
// Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
// Constraints:
// 1 <= s.length <= 100
// s contains only digits and may contain leading zero(s).
// MY OWN SOLUTION:
// I had this question on an interview I had, time was limited with 30 minutes.
// This was not the exact solution I came up with in 30 minutes. I optimized it but still it's exactly same in terms of structure.
var numDecodings = function(s) {
if(s[0] === "0") {
return 0 // No ways to decode
}
switch(s.length) {
case 1:
return 1
case 2:
if (parseInt(s) > 26) {
return s[1] === "0" ? 0 : 1
} else {
return s[1] === "0" ? 1 : 2
}
default:
if(parseInt(s.substr(0,2)) > 26) {
return numDecodings(s.substr(1,s.length))
} else {
return numDecodings(s.substr(1,s.length)) + numDecodings(s.substr(2,s.length))
}
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment