leetcode

commit c6142948e35eeedb8a01b60ba77e2530454587d8
parent f8681a944ce6dfa01de18bebb9163457144c2938
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Fri, 26 May 2023 21:15:27 -0500

Completed decode ways using dp, recursion, and memoization

Diffstat:
A
decode-ways/decode-ways.dart
 | 
39
+++++++++++++++++++++++++++++++++++++++

1 file changed, 39 insertions(+), 0 deletions(-)
diff --git a/decode-ways/decode-ways.dart b/decode-ways/decode-ways.dart
@@ -0,0 +1,39 @@
+//Given a string input s that has only numbers
+//return the total number of possible ways to decode
+//the numbers assuming that 1 = A and so on all the way to
+//26 = z. Given this for *all values in the list there will be
+//multiple ways to express them by either including the value
+//before, after, or only the current. To solve this I used recursion
+//and memoization to remember the already computed permutations for the
+//last values thus saving on computing those again. Given this the time complexity
+//of this code is O(n).
+//Time: 263ms Beats: 83.33%
+//Memory: 143.5MB Beats: 16.67%
+
+class Solution {
+  Map<int,int> memo = {};
+  int numDecodings(String s) {
+    if(memo[s.length] != null){
+      return (memo[s.length] ?? 0);
+    }
+    if(s.length <= 1){
+      if(s.length != 0){
+        if(s[0] == '0'){
+          return 0;
+        }
+      }
+      return 1;
+    }
+    if(s[0] == '0'){
+      return 0;
+    }
+    int return_val = 0;
+    return_val += numDecodings(s.substring(1));
+    String second = s.substring(0,2);
+    if(int.parse(second) <= 26){
+      return_val += numDecodings(s.substring(2));
+    }
+    memo[s.length] = return_val;
+    return return_val;
+  }
+}