leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

house-robber-tle.dart (1392B)

      1 //Find max value that can be robbed from homes on a block where
      2 //adjacent houses can't be robbed.
      3 //Time: TLE
      4 //Memory: TLE
      5 class Solution {
      6   int rob(List<int> nums) {
      7       int max = 0;
      8       for(int i = 0 ; i < nums.length ; ++i){
      9           int current = maxRobbed(nums, i, {}, {});
     10           if(current > max){
     11               max = current;
     12           }
     13       }
     14       return max;
     15   }
     16   int maxRobbed(List<int> nums, int current_house , Set<int> no_rob_list, Map<String, int> memo){
     17       if(no_rob_list.contains(current_house)){
     18           return 0;
     19       }
     20       no_rob_list.add(current_house - 1);
     21       no_rob_list.add(current_house);
     22       no_rob_list.add(current_house + 1);
     23 
     24       if(nums.length == 0){
     25           return 0;
     26       }
     27       if(nums.length == 1){
     28           return nums[0];
     29       }
     30       String curr = "";
     31       for (int number in nums) {
     32          curr += nums.toString() + " ";
     33       } 
     34       curr += current_house.toString();
     35       if(memo[curr] != null){
     36           int ret_int =  (memo[curr] ?? 0);
     37           return ret_int;
     38       }
     39 
     40       int current_val = nums[current_house];
     41       int max = 0;
     42       for(int i = 0 ; i < nums.length ; ++i){
     43           int current = maxRobbed(nums, i, Set.from(no_rob_list),memo);
     44           if(current > max){
     45               max = current;
     46           }
     47       }
     48       memo[curr] = max + current_val;
     49       return max + current_val;
     50   }
     51 }