leetcode

commit 163acd39ada89470ae9da524fb6aac85efdb2629
parent 3f32877cbfeb9eaa9b4833fb7982e61d4b00e017
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sun, 28 May 2023 22:21:40 -0500

Completed jum game using dart

Diffstat:
A
jump-game/jump-game.dart
 | 
38
++++++++++++++++++++++++++++++++++++++

1 file changed, 38 insertions(+), 0 deletions(-)
diff --git a/jump-game/jump-game.dart b/jump-game/jump-game.dart
@@ -0,0 +1,38 @@
+//Given a list of numbers return if it is possible to make it
+//to the end of the list where you are only able to jump at most the number of
+//spots on the current nums value. To solve this I used DP, recursion, and memoization.
+//I chose to use a list instead of a set because the set was getting too big and since we know
+//how long the list will be a list works well for this because of its constant time checks.
+
+//Note: I was running into many issues with sets
+//as well as shortening the list each time. Sublists
+//do not work on this problem because they take linear time
+//to create as opposed to indexes which work much faster.
+
+//Time: 623ms Beats: 14.29%
+//Memory: 167.3MB Beats: 7.14%
+class Solution {
+  List<bool> memo = [];
+  bool canJump(List<int> nums) {
+      memo = List.filled(nums.length , false);
+      return jump(nums, 0);
+  }
+  bool jump(List<int> nums , int index){
+      if(memo[index]){
+          return false;
+      }
+      memo[index] = true;
+      if(nums.length - 1 == index || nums[index] + index >= nums.length){
+          return true;
+      }
+      if(nums[index] == 0){
+          return false;
+      }
+      for(int i = 0 ; i < nums[index] ; ++i){
+          if(jump(nums, index + i + 1)){
+              return true;
+          }
+      }
+      return false;
+  }
+}