# C++ solution with dfs and string encoding.

• 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;
}
};
``````

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