ankityadav107
diff --git a/‎08 August Leetcode Challenge 2021/18_decodeWays.cpp
Copy file name to clipboard
+17Lines changed: 17 additions & 0 deletions b/‎08 August Leetcode Challenge 2021/18_decodeWays.cpp
Copy file name to clipboard
+17Lines changed: 17 additions & 0 deletions
@@ -0,0 +1,17 @@
+class Solution { 
+public:
+    int memo[100] = {};
+    int numDecodings(const string& s) {
+        return dp(s, 0);
+    }
+    int dp(const string& s, int i) {
+        if (i == s.size()) return 1;
+        if (memo[i] != 0) return memo[i];
+        int ans = 0;
+        if (s[i] != '0') // Single digit
+            ans += dp(s, i+1);
+        if (i+1 < s.size() && (s[i] == '1' || s[i] == '2' && s[i+1] <= '6')) // Two digits
+            ans += dp(s, i+2);
+        return memo[i] = ans;
+    }
+};