32ms sort and dfs solution


  • 0
    C

    Build a graph to record city list which can be reached from one city, and the list will be sorted, so that we got the smallest lexical order path.

    //path got when getting ori
    //if find the answer return true
    bool dfs(vector<string>& path, int curTic, int totalTic, const string& ori, unordered_map<string, vector<pair<string, bool>>>& linkMap)
    {
        if(curTic == totalTic)
        {
            return true;
        }
        if(linkMap.find(ori) != linkMap.end())
        {
            vector<pair<string, bool>> &nei = linkMap[ori];
            for(int i = 0; i < nei.size(); i++)
            {
                if(!nei[i].second)  //if not visited
                {
                    path.push_back(nei[i].first);
                    nei[i].second = true;
                    if(dfs(path, curTic + 1, totalTic, nei[i].first, linkMap))
                    {
                        return true; 
                    }
                    path.pop_back();
                    nei[i].second = false;
                }
            }
        }
        return false;
    }
    
    class Solution 
    {
    public:
        vector<string> findItinerary(vector<pair<string, string>> tickets) 
        {
            unordered_map<string, vector<pair<string, bool>>> linkMap;
            for(int i = 0; i < tickets.size(); i++)
            {
                linkMap[tickets[i].first].push_back(make_pair(tickets[i].second, false));
            }
            for(auto it = linkMap.begin(); it != linkMap.end(); it++)
            {
                sort(it->second.begin(), it->second.end());
            }
            vector<string> path;
            path.push_back("JFK");
            dfs(path, 0, tickets.size(), "JFK", linkMap);
            return path;
        }
    };

Log in to reply
 

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