23ms solution using adjacency matrix


  • 0
    F
    class Solution {
    public:
        unordered_map<string, int> _cityIdxMap;
        vector<string> _cityVec;
    
       bool dfs(vector<vector<int>> &flights, int nRest, int from, vector<string> &ans)
        {
            ans.push_back( _cityVec[from] );
            if(nRest == 0) return true;
            for(int t=0; t<_cityVec.size(); ++t) {
                if(flights[from][t] > 0) {
                    flights[from][t]--;
                    if(dfs(flights, nRest-1, t, ans)) return true;
                    flights[from][t]++;
                }
            }
            ans.pop_back();
            return false;
        }
    
        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            for( const auto &flight : tickets) {
                _cityIdxMap[flight.first] = 0;
                _cityIdxMap[flight.second] = 0;
            }
            for(const auto &cityIdx : _cityIdxMap) {
                _cityVec.push_back(cityIdx.first);
            }
            sort(_cityVec.begin(), _cityVec.end());
            for(int i=0; i<_cityVec.size(); ++i) {
                _cityIdxMap[ _cityVec[i] ] = i;
            }
    
            vector<vector<int>> flights(_cityVec.size(), vector<int>(_cityVec.size(), 0));
            for(const auto &t : tickets) {
                int fromIdx = _cityIdxMap[ t.first ];
                int toIdx = _cityIdxMap[ t.second ];
                flights[fromIdx][toIdx]++;
            }
            vector<string> ans;
            dfs(flights, tickets.size(), _cityIdxMap["JFK"], ans);
            return ans;
        }
    };
    

Log in to reply
 

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