Iteration version DFS


  • 0
    L

    My first thought was to use recursive backtracking. Since the largest size is 10^4, it would overflow the stack with recursive method. So I simply convert the recursive version into iterative version. Maybe this is why BFS is much simpler. This is just for illustration. Code is tediously long.

    public boolean sequenceReconstruction(int[] org, int[][] seqs) {
            if (seqs.length == 0)
                return false;
            Map<Integer, List<Integer>> edges = new HashMap<>();
            boolean[] hasParents = new boolean[org.length + 1];
            for (int row = 0 ; row < seqs.length ; row ++) {
                for (int col = 0 ; col < seqs[row].length ; col ++) {
                    if (seqs[row][col] > org.length || seqs[row][col] <= 0)
                        return false;
                    if (col > 0)
                        hasParents[seqs[row][col]] = true;
                    if (!edges.containsKey(seqs[row][col]))
                        edges.put(seqs[row][col], new ArrayList<>());
                    if (col <= seqs[row].length - 2)
                        edges.get(seqs[row][col]).add(seqs[row][col + 1]);
                }
            }
            int root = -1;
            int countOfRoots = 0;
            for (int i = 1 ; i < hasParents.length ; i ++) {
                if (!hasParents[i]) {
                    root = i;
                    countOfRoots ++;
                }
            }
            if (countOfRoots != 1)
                return false;
                
            int countOfOrders = 0;
            int[] resOrder = new int[org.length];
            int[] aux = new int[org.length];
            Stack<MyClass> stack = new Stack<>();
            stack.push(new MyClass(root, 0));
            while (!stack.empty()) {
                MyClass cur = stack.pop();
                if (cur.depth >= resOrder.length) {
                    return false;
                }
                aux[cur.depth] = cur.val;
                List<Integer> chil = edges.get(cur.val);
                if (chil.size() == 0) {
                    if (cur.depth == resOrder.length - 1) {
                        if (countOfOrders == 0) {
                            for (int chck = 0 ; chck < resOrder.length ; chck ++) {
                                resOrder[chck] = aux[chck];
                            }
                            countOfOrders ++;
                        } else {
                            for (int chck = 0 ; chck < resOrder.length ; chck ++) {
                                if (resOrder[chck] != aux[chck]) {
                                    return false;
                                }
                            }
                        }
                    }
                }
                for (Integer next : chil) {
                    MyClass nextChil = new MyClass(next, cur.depth + 1);
                    stack.push(nextChil);
                }
            }
            for (int i = 0 ; i < resOrder.length ; i ++) {
                if (org[i] != resOrder[i]) {
                    return false;
                }
            }
            return true;
        }
        private class MyClass {
            int val;
            int depth;
            public MyClass(int newVal, int newDepth){
                val = newVal;
                depth = newDepth;
            }
        }

  • 0

    what conditions you used in the DFS to check validation?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.