Problem
Given a list of sorted words in a hypothetical language(assuming it has subset of english alphabets), determine the sorted order of characters.
e.g. sorted words = { ntr , car , arc, act , tan }
Sorted characters : n r c a t
It should add another word at the end to determine the order n and r, I add tar
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find dictionary order
Created Date : 27-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <hash_map>
#include <algorithm>
#include <set>
using namespace std;
void ComputePartialOrder(vector<string>& dict, vector<pair<char, int>>& order)
{
hash_map<char, int> s;
set<pair<char, char>> orderPair;
for(int i = 0; i < dict.size(); ++i)
{
for(int j = 0; j < dict[i].size(); ++j){
s.insert(make_pair(dict[i][j], 0));
}
}
for(int i = 0; i < dict.size() - 1; ++i){
string str1 = dict[i];
string str2 = dict[i + 1];
int j = 0;
while(str1[j] == str2[j]){
j ++;
}
orderPair.insert(make_pair(str1[j], str2[j]));
}
bool changed = true;
while(changed)
{
changed = false;
for(auto it = orderPair.begin(); it != orderPair.end(); ++it){
int ord1 = s[it->first];
int ord2 = s[it->second];
if(ord2 != max(ord1 + 1, ord2)){
changed = true;
s[it->second] = max(ord1 + 1, ord2);
}
}
}
cout << "----------------------------" << endl;
for(auto it = s.begin(); it != s.end(); ++ it){
order.push_back(make_pair(it->first, it->second));
}
sort(order.begin(), order.end(),
[=](pair<char, int> i, pair<char, int> j)->bool
{return i.second < j.second;});
for(auto it = order.begin(); it != order.end(); ++it){
cout << it->first << "----" << it->second << endl;
}
}
int main(int argc, char* argv[])
{
vector<string> dict;
vector<pair<char, int>> order;
dict.push_back("ntr");
dict.push_back("car");
dict.push_back("arc");
dict.push_back("act");
dict.push_back("tan");
dict.push_back("tar");
ComputePartialOrder(dict, order);
return 0;
}
Output
----------------------------
n----0
r----1
c----2
a----3
t----4
Press any key to continue . . .