leetcode

commit d3b06283e4190fc81aaf469663ed46bfb9272901
parent 163acd39ada89470ae9da524fb6aac85efdb2629
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sun, 28 May 2023 22:29:11 -0500

Completed jump game with better solution

Diffstat:
A
jump-game/jump-gameV2.dart
 | 
30
++++++++++++++++++++++++++++++

1 file changed, 30 insertions(+), 0 deletions(-)
diff --git a/jump-game/jump-gameV2.dart b/jump-game/jump-gameV2.dart
@@ -0,0 +1,30 @@
+//This reverses the direction of searches in the for
+//loop to check the furthest forward jump first to speed up
+//movement.
+//Time: 541ms Beats: 14.29%
+//Memory: 166.8MB 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 = nums[index]; i > 0 ; --i){
+          if(jump(nums, index + i)){
+              return true;
+          }
+      }
+      return false;
+  }
+}