Short Ruby / Python / Java / C++


  • 244

    Just Eulerian path. Greedy DFS, building the route backwards when retreating.

    More explanation and example under the codes.

    Iterative versions inspired by fangyang (I had only thought of recursion, d'oh).


    Ruby

    def find_itinerary(tickets)
      tickets = tickets.sort.reverse.group_by(&:first)
      route = []
      visit = -> airport {
        visit[tickets[airport].pop()[1]] while (tickets[airport] || []).any?
        route << airport
      }
      visit["JFK"]
      route.reverse
    end
    

    Iterative version:

    def find_itinerary(tickets)
      tickets = tickets.sort.reverse.group_by(&:first)
      route, stack = [], ["JFK"]
      while stack.any?
        stack << tickets[stack[-1]].pop()[1] while (tickets[stack[-1]] || []).any?
        route << stack.pop()
      end
      route.reverse
    end
    

    Python

    def findItinerary(self, tickets):
        targets = collections.defaultdict(list)
        for a, b in sorted(tickets)[::-1]:
            targets[a] += b,
        route = []
        def visit(airport):
            while targets[airport]:
                visit(targets[airport].pop())
            route.append(airport)
        visit('JFK')
        return route[::-1]
    

    Iterative version:

    def findItinerary(self, tickets):
        targets = collections.defaultdict(list)
        for a, b in sorted(tickets)[::-1]:
            targets[a] += b,
        route, stack = [], ['JFK']
        while stack:
            while targets[stack[-1]]:
                stack += targets[stack[-1]].pop(),
            route += stack.pop(),
        return route[::-1]
    

    Java

    public List<String> findItinerary(String[][] tickets) {
        for (String[] ticket : tickets)
            targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
        visit("JFK");
        return route;
    }
    
    Map<String, PriorityQueue<String>> targets = new HashMap<>();
    List<String> route = new LinkedList();
    
    void visit(String airport) {
        while(targets.containsKey(airport) && !targets.get(airport).isEmpty())
            visit(targets.get(airport).poll());
        route.add(0, airport);
    }
    

    Iterative version:

    public List<String> findItinerary(String[][] tickets) {
        Map<String, PriorityQueue<String>> targets = new HashMap<>();
        for (String[] ticket : tickets)
            targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
        List<String> route = new LinkedList();
        Stack<String> stack = new Stack<>();
        stack.push("JFK");
        while (!stack.empty()) {
            while (targets.containsKey(stack.peek()) && !targets.get(stack.peek()).isEmpty())
                stack.push(targets.get(stack.peek()).poll());
            route.add(0, stack.pop());
        }
        return route;
    }
    

    C++

    vector<string> findItinerary(vector<pair<string, string>> tickets) {
        for (auto ticket : tickets)
            targets[ticket.first].insert(ticket.second);
        visit("JFK");
        return vector<string>(route.rbegin(), route.rend());
    }
    
    map<string, multiset<string>> targets;
    vector<string> route;
    
    void visit(string airport) {
        while (targets[airport].size()) {
            string next = *targets[airport].begin();
            targets[airport].erase(targets[airport].begin());
            visit(next);
        }
        route.push_back(airport);
    }
    

    Explanation

    First keep going forward until you get stuck. That's a good main path already. Remaining tickets form cycles which are found on the way back and get merged into that main path. By writing down the path backwards when retreating from recursion, merging the cycles into the main path is easy - the end part of the path has already been written, the start part of the path hasn't been written yet, so just write down the cycle now and then keep backwards-writing the path.

    Example:

    enter image description here

    From JFK we first visit JFK -> A -> C -> D -> A. There we're stuck, so we write down A as the end of the route and retreat back to D. There we see the unused ticket to B and follow it: D -> B -> C -> JFK -> D. Then we're stuck again, retreat and write down the airports while doing so: Write down D before the already written A, then JFK before the D, etc. When we're back from our cycle at D, the written route is D -> B -> C -> JFK -> D -> A. Then we retreat further along the original path, prepending C, A and finally JFK to the route, ending up with the route JFK -> A -> C -> D -> B -> C -> JFK -> D -> A.


  • 10

    I feel really stupid now. I remember doing something like this when I was a kid and even had no PC, just by painting over maps with a pencil. Now I've failed to realize that it's the same thing. Gotta read up something on graph theory now.


  • 2

    Since you are using LinkedList why not just addFirst instead of add(0, airport)?


  • 1

    @stachenov Sorry :-P

    @dietpepsi Because List doesn't have addFirst, only LinkedList does. Though I must admit I also just didn't know it :-). Though that's because I only looked at the List API :-)


  • 0

    Cool~

    I replaced my ArrayList with LinkedList when I saw addFirst API.


  • 2
    S

    Could you explain a little about the basics of your idea?
    e.g.
    A->B, A-C, C->A.

    Why A->B is the last trip if there is no way to go from B and the trips pool is not empty


  • 0
    This post is deleted!

  • 8

    Because I build the route backwards. From A the solution first visits B but didn't put anything into the route yet. Then when it's stuck at B, it puts B at the end of the route. The recursion retreats to A, where the A->C->A cycle will be found and inserted into the route before the B.


  • 2

    I added some more explanation and an example under my solutions.


  • 1
    G

    quick question regarding the python solutions. I think I figured out why you sort before putting the tickets into a dict (in order for the destinations to be in lexicographic order, right? has nothing to do with the start). But why do you use sorted(arg)[::-1] vs sorted(arg, reverse=True). Is there an advantage?


  • 1

    @grodrigues3 Yes, for the lexicographic order. And [::-1] just because it's shorter. Curious about speed, I ran this test which didn't really show a difference:

    >>> tickets = [[str(a), str(b)] for a in range(100, 200) for b in range(100, 120)]
    >>> import random, timeit
    >>> random.shuffle(tickets)
    >>> timeit.timeit(lambda: sorted(tickets)[::-1], number=1000)
    2.795679170729204
    >>> timeit.timeit(lambda: sorted(tickets, reverse=True), number=1000)
    2.8045106994406526
    >>> timeit.timeit(lambda: sorted(tickets)[::-1], number=1000)
    2.8009243341714978
    >>> timeit.timeit(lambda: sorted(tickets, reverse=True), number=1000)
    2.794430261199775
    

    Not very surprising, given that [::-1] alone is much much faster:

    >>> timeit.timeit(lambda: tickets[::-1], number=1000)
    0.026649176373979344
    >>> timeit.timeit(lambda: tickets[::-1], number=1000)
    0.02277094986402517
    

    Also, that's just a small part of the solution, so overall it will play an even smaller role. It does create a new list, of course, which might be a downside sometimes.


  • 0
    A

    Just so you know, in the java version, Map.computeIfAbsent() seems to be really slow compared with an if statement with Map.containsKey(), according to the OJ, and could you please explain why thats the case? Thanks much!


  • 1

    It's not computeIfAbsent, it's lambdas. If you replace the lambda with an ugly anonymous class, it will work 20 times faster or so (and slightly faster than containsKey because you don't look up the key twice). That's probably because the OJ doesn't include lambda warm-up phase in its benchmarks. See my question about that on StackOverflow.


  • 0

    @aiscong Yes, I know, but thanks anyway. I decided to keep it because I think it's the right way to do it and that the ridiculous slowness is a fault of Java that will hopefully eventually get fixed.

    @stachenov Thanks for the info and the link.


  • 1

    Just to make it clear: it's not a fault of Java, it's a fault of LeetCode. Because initialization only happens once, and once it happened, lambdas start to work pretty fast. It becomes clear when you try to use lambdas multiple times and it doesn't affect performance, and it can also be seen that any use of lambdas just add some constant to runtime (about 70-75 ms), not increase it by factor.


  • 0

    Huh? How is it LeetCode's fault that Java takes so long for the initialization?


  • 0

    Initialization is just initialization. You don't include VM startup time for any language in the benchmark for your algorithm, right? Because you would get a lot then not just for Java, but for .Net and other similar frameworks. Why do you include lambda facility initialization time then? Because it's not a part of you algorithm execution time unless you run it for the first time, and measuring performance based on the first run only is kind of silly.


  • 1

    I disagree. That's not at all like VM startup. VM startup is necessary. For all solutions. The lambda initialization stuff is strictly my choice if I use it. I'm responsible for that extra cost. And Java is responsible for that extra cost being so large. I can be blamed and Java can be blamed, but not LeetCode. LeetCode is neither responsible for Java having that cost for that feature nor responsible for me choosing that feature.


  • 0

    I don't get it. If Java included lambda initialization in the VM startup (and I don't think anyone would notice additional 75 ms there), then you'd be OK with it, but since it decides to initialize it lazily, then it is suddenly Java's fault? I would understand it if it increased runtime of each call, but it doesn't. If the OJ used just one lambda somewhere in its initialization procedures, then we'd hardly noticed any difference.


  • 0
    K

    Python iterative version is awesome! It's surprising that sorted(tickets)[::-1] is faster than sorted(tickets, reverse=True) according to my test :-) If so, why offering reverse option for sorted() ...


Log in to reply
 

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