Could anybody show me how to consider the time complexity of this kind of code?

  • 0

    In this question, I used a map<string, set<string>> to record each flight and do dfs & backtracking.

    However, the size of each set is not fixed. What's the right way to think about the time complexity?

    Here is my code.

    class Solution {
        bool dfs(unordered_map<string, set<string>> &graph, vector<string> &res, int count, string depart) {
            // Get all tickets.
            if (count == 0) return true;
            // No more tickets at current location.
            else if (graph[depart].size() == 0) return false;
            else {
                set<string>::iterator lastIter, curIter = graph[depart].begin();
                while (curIter != graph[depart].end()) {
                    string temp = *curIter;
                    lastIter = curIter++;
                    // We need erase the choice of arrival then add it back after dfs.
                    if (dfs(graph, res, count - 1, temp)) {
                        return true;
                return false;
        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            vector<string> res;
            if (tickets.size() != 0) {
                // Build the graph, use set to sort the arrivals.
                unordered_map<string, set<string>> graph;
                for (auto t:tickets) {
                if (dfs(graph, res, tickets.size(), "JFK")) {
                    reverse(res.begin(), res.end());
            return res;

Log in to reply

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