LeetCode June Challenge - Day 28

Problem: LeetCode June Challenge - Day 28

Ideas

  1. Find an Eulerian Path in the graph given.
  2. Here are some implementation details:
    • I used a hash map to store the graph, so I didn’t need to assign integers to the strings.
    • For each vertex I store a vector with the possible destinations. I also store in a hash map theindex of the last vertex I visited, which simulates deleting edges.

Solution:

class Solution {
    unordered_map<string, vector<string>> m;
    unordered_map<string, int> index;
    vector<string> ans;
    string start = "JFK";

    void construct_graph(vector<vector<string>>& tickets){
        for(vector<string>& f : tickets)
            m[f[0]].push_back(f[1]);
        for(auto& p : m)
            sort(p.second.begin(), p.second.end());
    }

    void dfs(const string& u){
        while(index[u] < m[u].size()){
            string v = m[u][index[u]++];
            dfs(v);
        }
        ans.push_back(u);
    }

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        construct_graph(tickets);
        dfs(start);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};