online advertising

## Sunday, February 14, 2016

### LeetCode OJ - Reconstruct Itinerary

Problem:

Please find the problem here.

Solution:

The problem wasn't very explicit, but in fact it is asking for a path that use all the tickets. I just used recursive backtracking for the purpose.

The algorithm can be further improved by replacing the vector<string, bool> (as a list of available/used destination) to a data structure that allow us to remove and iterate fast. A doubly linked list will serve the purpose. I thought of something similar when I tried N-Queens.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/reconstruct-itinerary/

#include "LEET_RECONSTRUCT_ITINERARY.h"
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_RECONSTRUCT_ITINERARY
{
class Solution
{
public:
vector<string> findItinerary(vector<pair<string, string>> tickets)
{
map<string, vector<pair<string, bool>>> dest;

// Step 1: Build the map
for (size_t i = 0; i < tickets.size(); i++)
{
string src = tickets[i].first;
string dst = tickets[i].second;
map<string, vector<pair<string, bool>>>::iterator probe = dest.find(src);
if (probe == dest.end())
{
dest.insert(pair<string, vector<pair<string, bool>>>(src, vector<pair<string, bool>>()));
}
dest[src].push_back(pair<string, bool>(dst, true));
}

// Step 2 : Sort the destination vector
for (map<string, vector<pair<string, bool>>>::iterator di = dest.begin(); di != dest.end(); di++)
{
sort(di->second.begin(), di->second.end());
}
vector<string> soln;
soln.push_back("JFK");
this->findItinerary("JFK", soln, tickets.size() + 1, dest);
return soln;
}

bool findItinerary(string current, vector<string>& soln, int goal, map<string, vector<pair<string, bool>>>& dest)
{
map<string, vector<pair<string, bool>>>::iterator probe = dest.find(current);
if (probe == dest.end())
{
return (soln.size() == goal);
}
else
{
vector<pair<string, bool>> & dstvector = probe->second;
for (size_t i = 0; i < dstvector.size(); i++)
{
if (dstvector[i].second)
{
dstvector[i].second = false;
soln.push_back(dstvector[i].first);
if (findItinerary(dstvector[i].first, soln, goal, dest))
{
return true;
}
soln.pop_back();
dstvector[i].second = true;
}
}
return (soln.size() == goal);
}
}
};
};

using namespace _LEET_RECONSTRUCT_ITINERARY;

int LEET_RECONSTRUCT_ITINERARY()
{
Solution solution;
vector<pair<string, string>> itin;
// [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
//itin.push_back(pair<string, string>("MUC", "LHR"));
//itin.push_back(pair<string, string>("JFK", "MUC"));
//itin.push_back(pair<string, string>("SFO", "SJC"));
//itin.push_back(pair<string, string>("LHR", "SFO"));

// [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
//itin.push_back(pair<string, string>("JFK", "SFO"));
//itin.push_back(pair<string, string>("JFK", "ATL"));
//itin.push_back(pair<string, string>("SFO", "ATL"));
//itin.push_back(pair<string, string>("ATL", "JFK"));
//itin.push_back(pair<string, string>("ATL", "SFO"));

// [["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]]
itin.push_back(pair<string, string>("JFK", "KUL"));
itin.push_back(pair<string, string>("JFK", "NRT"));
itin.push_back(pair<string, string>("NRT", "JFK"));

vector<string> result = solution.findItinerary(itin);
for (size_t i = 0; i < result.size(); i++)
{
cout << result[i] << endl;
}
return 0;
}