C++ solution with dfs and string encoding.


  • 0
    Y

    i think encode string maybe faster. and string only have 3 characters.
    my solution defeat 70%

    class Solution {
    public:
        inline int encode(const std::string& str) {
            return (str[2] - 'A') + (str[1] - 'A') * 26 + (str[0] - 'A') * 26 * 26;
        }
        inline std::string decode(int num) {
            char a = num - num / 26 * 26 + 'A';
            char b = num / 26 - num / (26 * 26) * 26 + 'A';
            char c = num / 26 / 26 + 'A';
            return {c, b, a};
        }
        
        bool search(unordered_map<int, vector<pair<int, int>>>& graph, int offset, int depth, int* mem, int tick_num) {
            if (depth == tick_num) return true;
            const int& current = mem[depth];
            for (; offset < graph[current].size(); ++offset) {
                if (graph[current][offset].second) continue;
                graph[current][offset].second = 1;
                mem[depth + 1] = graph[current][offset].first;
                bool ok = search(graph, 0, depth + 1, mem, tick_num);
                if (ok) return true;
                graph[current][offset].second = 0;
            }
            return false;
        }
        
        vector<string> findItinerary(vector<pair<string, string>> tickets) {
            unordered_map<int, vector<pair<int, int>>> graph;
            int jfk = encode("JFK");
            for (auto& u : tickets) {
                graph[encode(u.first)].push_back(pair<int, int>(encode(u.second), 0));
            }
            for (auto ptr = graph.begin(); ptr != graph.end(); ++ptr) {
                sort(ptr->second.begin(), ptr->second.end());
            }
            
            int tick_num = tickets.size();
            int* mem = (int*)calloc(sizeof(int), tickets.size() + 1);
            mem[0] = jfk;
            int ok = search(graph, 0, 0, mem, tick_num);
            vector<string> ret;
            for (int n = 0; n <= tick_num; ++n) {
                ret.push_back(decode(mem[n]));
            }
            return ret;
        }
    };
    

Log in to reply
 

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