C# Iterative version with detail comments


  • 0

    this solution will be shorter if C# has built-in priority queue library.....

    Inspired by @StefanPochmann approach, basically it's his idea in C# verison.

    It works well and can handle test cases that contains invalid itineraries. Like [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"]] .

    Time: Assume we have N itineraries, each itinerary has two string=> 2N strings.

    1. we build hashtable for all itineraries. O(N) time
    2. we sort values string for each key. O(N* NlogN) time
    3. we backtracking to find the next city we want, until all city has added. Since we use hashtable in the searching so it's O(N).
      4.Convert out result linkedlist to a list, not sure if it's O(N) or O(1) in C# but can never greater than O(N).

    Adding together it’s O(N*logN) time.

    Space: we use a hash table and a stack, so it's O(2N)=>O(N) space

               public IList<string> FindItinerary(string[,] tickets)
                {
                    LinkedList<string> res= new LinkedList<string>();
                    //invalid input
                    if (tickets == null || tickets.Length == 0) return res.ToList();
                    //Build a hashtable/dict for route. 
                    //key is the source city, value are all the destination city from source city.
                    var routeDict = new Dictionary<string, List<string>>();
                    
                    int count = tickets.GetLength(0);   //tickets number
                    for (int i = 0; i < count; i++)
                    {
                        var source = tickets[i, 0];
                        var dest = tickets[i, 1];
    
                        if(!routeDict.ContainsKey(source))
                            routeDict.Add(source, new List<string>());
    
                        routeDict[source].Add(dest);
                    }
                    //keep asce order 
                    foreach (var list in routeDict.Values)  list.Sort();
    
                    //need a stack as like a backtracking route from final.
                    Stack<string> stack = new Stack<string>();
                    stack.Push("JFK");    //Add start city
                    while (stack.Any())
                    {
                        while (routeDict.ContainsKey(stack.Peek()) && routeDict[stack.Peek()].Any())
                        {
                            var next = routeDict[stack.Peek()].First();  //the next city from the source city in lexical order
                            routeDict[stack.Peek()].RemoveAt(0);         //remove the next city from the hash table.(since List<T> doesn't has Poll/Pop/Dequeue)
                            stack.Push(next);                            //push next city into the stack
                        }
                        res.AddFirst(stack.Pop());                      //Pop all the city from stack, Add them in the head of res.
                    }
                    return res.ToList();
                }
    
    

Log in to reply
 

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