package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.TreeSet;

/**
 * https://leetcode.com/problems/reconstruct-itinerary/
 */
public class Problem332 {
    public List<String> findItinerary(String[][] tickets) {
        Map<String, TreeSet<Ticket>> map = new HashMap<>();
        for (String[] ticket : tickets) {
            String from = ticket[0];
            String to = ticket[1];
            if (!map.containsKey(from)) {
                Ticket t = new Ticket(from, to);
                TreeSet<Ticket> set = new TreeSet<>();
                set.add(t);
                map.put(from, set);
            } else {
                map.get(from).add(new Ticket(from, to));
            }
        }
        List<String> result = new ArrayList<>();
//        String from = "JFK";
//        result.add(from);
//        TreeSet<Ticket> set = map.get(from);
//        while (set != null && set.size() > 0) {
//            Ticket ticket = set.pollFirst();
//            from = ticket.to;
//            result.add(from);
//            set = map.get(from);
//        }
        result.add("JFK");
        return findItinerary(map, tickets.length, "JFK", 0, result);
    }

    private List<String> findItinerary(Map<String, TreeSet<Ticket>> map, int max, String name,
                                       int count, List<String> result) {
        if (count == max) {
            return result;
        }
        TreeSet<Ticket> tickets = map.get(name);
        if (tickets != null) {
            for (Ticket ticket : tickets) {
                List<String> newList = new ArrayList<>(result);
                newList.add(ticket.to);
                List<String> r = findItinerary(map, max, ticket.to, count + 1, newList);
                if (!r.isEmpty()) {
                    return r;
                }
            }
        }
        return new ArrayList<>();
    }

    private static class Ticket implements Comparable<Ticket> {
        private final String from;
        private final String to;

        public Ticket(String from, String to) {
            this.from = from;
            this.to = to;
        }

        @Override
        public int compareTo(Ticket o) {
            return to.compareTo(o.to);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Ticket ticket = (Ticket) o;
            return Objects.equals(from, ticket.from) &&
                Objects.equals(to, ticket.to);
        }

        @Override
        public int hashCode() {
            return Objects.hash(from, to);
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder();
            sb.append("[").append(from).append(", ").append(to).append("]");
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        Problem332 prob = new Problem332();
//        System.out.println(prob.findItinerary(new String[][]{
//            {"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}
//        }));
        System.out.println(prob.findItinerary(new String[][]{
            {"JFK", "SFO"}, {"JFK", "ATL"}, {"SFO", "ATL"}, {"ATL", "JFK"}, {"ATL", "SFO"}
        }));
//        System.out.println(prob.findItinerary(new String[][]{
//            {"JFK", "KUL"}, {"JFK", "NRT"}, {"NRT", "JFK"}
//        }));
    }
}

@@ -62,24 +62,50 @@
 il.HashMap;%0A
+import java.util.HashSet;%0A
 import java.
@@ -163,16 +163,38 @@
 bjects;%0A
+import java.util.Set;%0A
 import j
@@ -901,322 +901,8 @@
 ();%0A
-//        String from = %22JFK%22;%0A//        result.add(from);%0A//        TreeSet%3CTicket%3E set = map.get(from);%0A//        while (set != null && set.size() %3E 0) %7B%0A//            Ticket ticket = set.pollFirst();%0A//            from = ticket.to;%0A//            result.add(from);%0A//            set = map.get(from);%0A//        %7D%0A
     
@@ -983,16 +983,33 @@
 JFK%22, 0,
+ new HashSet%3C%3E(),
  result)
@@ -1161,16 +1161,37 @@
 t count,
+ Set%3CTicket%3E visited,
  List%3CSt
@@ -1387,32 +1387,128 @@
 et : tickets) %7B%0A
+                if (visited.contains(ticket)) %7B%0A                    continue;%0A                %7D%0A
                 
@@ -1587,32 +1587,137 @@
 add(ticket.to);%0A
+                Set%3CTicket%3E newVisited = new HashSet%3C%3E(visited);%0A                newVisited.add(ticket);%0A
                 
@@ -1778,16 +1778,28 @@
 unt + 1,
+ newVisited,
  newList
@@ -3064,18 +3064,16 @@
 m332();%0A
-//
         
@@ -3118,34 +3118,32 @@
 new String%5B%5D%5B%5D%7B%0A
-//
             %7B%22MU
@@ -3201,18 +3201,16 @@
  %22SFO%22%7D%0A
-//
         
@@ -3380,18 +3380,16 @@
    %7D));%0A
-//
         
@@ -3442,18 +3442,16 @@
 ng%5B%5D%5B%5D%7B%0A
-//
         
@@ -3501,18 +3501,16 @@
  %22JFK%22%7D%0A
-//
         

Update problem 332