leetcode

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

all-paths-from-source-to-target.dart (1372B)

      1 //Return a list of all possible paths that lead to the highest node starting from 0.
      2 //The input list is a list of edges for each node thus a list of lists.
      3 //The time complexity of this code is O(k^n) where n is the number of nodes and
      4 //k is the number of edges per node (assuming an equal number of edges per node which is not given).
      5 //Time: 425ms Beats: 50%
      6 //Memory: 156.8MB Beats: 50%
      7 
      8 class Solution {
      9   List<List<int>> paths = [];
     10   int highest_val = 0;
     11   List<List<int>> graph = [];
     12   List<List<int>> allPathsSourceTarget(List<List<int>> graph_in) {
     13       graph = graph_in;
     14       for(int i = 0 ; i < graph.length ; ++i){
     15           for(int x = 0 ; x < graph[i].length ; ++x){
     16               if(graph[i][x] > highest_val){
     17                   highest_val = graph[i][x];
     18               }
     19           }
     20       }
     21       recurse([0]);
     22       return paths;
     23   }
     24 
     25   void recurse(List<int> visited){
     26       print(visited);
     27       if(visited[visited.length - 1] == highest_val){
     28           paths.add(visited);
     29           return;
     30       }
     31       for(int i = 0 ; i < graph[visited[visited.length - 1]].length; ++i){
     32           if(visited.contains(graph[visited[visited.length - 1]][i]) == false){
     33             List<int> next_visited = List<int>.from(visited);
     34             next_visited.add(graph[visited[visited.length - 1]][i]);
     35             recurse(next_visited);
     36           }
     37       }
     38   }
     39 
     40 
     41 }