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


  • 0
    S

    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 {
    public:
        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.
                    graph[depart].erase(lastIter);
                    if (dfs(graph, res, count - 1, temp)) {
                        res.push_back(temp);
                        return true;
                    }
                    graph[depart].insert(temp);
                }
                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) {
                    graph[t.first].insert(t.second);
                }
                if (dfs(graph, res, tickets.size(), "JFK")) {
                    res.push_back("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.