UVA – 10150 – Doublets

  • Problem StatmentUVA – 10150 – Doublets
  • Type : BFS
  • Solution :
    • The Problem can be modeled as graph shortest path problem where an Undirected edge between two strings indicates that they are doublets.
    • traverse from the source to the destination and go back recursively when u find a solution to print it out.
  • Optimization :
    • Collect strings with the same size at the beginning together to save time in searching for doublets.
    • No need to construct a graph just traverse through the strings with the same size and use a bool function to check for doublets.
    • Use a recursive method to construct the solution, it saves you lines of code and special cases
  • Gotchas :
    • the source and the destination given may not have been mentioned before in the words dictionary
    • the source and the destination might be the same.
    • the two doublets should be with the same size but differ in 1 letter. (i.e [sami], [samia] are not doublets)
  • Other People’s Solutions:-
  • Mine was the shortest  XD XD 😀 😛 😛
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <string.h>

using namespace std;

#define MAX 26000
int parent[MAX];
bool doublets(string a, string b) {
	int d=0;
	for (size_t i = 0; i < a.length(); i++)	d+= (a[i]!=b[i]);
	return d==1;
}
void printPath(int ai, int zi, vector<string> ws) {
	if (ai != zi)
		printPath(ai, parent[zi], ws);
	cout << ws[zi] << endl;
}
int main() {

	string a, z, word;
	vector<string> words[MAX];
	while (getline(cin, word) && word.size()) {
		if(words[word.size()].empty()) words[word.size()].push_back(""); // sentiel to start @ i=1.
		words[word.size()].push_back(word);
	}

	int CASE = 0;
	while ((cin >> a >> z)) {
		if (CASE++)
			cout << endl;
		vector<string> ws = words[a.size()];
		size_t ai = find(ws.begin(), ws.end(), a) - ws.begin();
		size_t zi = find(ws.begin(), ws.end(), z) - ws.begin();

		if (a.size() != z.size() || ai == ws.size() || zi == ws.size())
			cout << "No solution." << endl;
		else {
			memset(parent, 0, sizeof parent);
			parent[ai] = ai;
			queue<size_t> q;
			q.push(ai);
			while (q.size() && q.front() != zi) {
				int u = q.front();
				q.pop();
				for (size_t v = 0; v < ws.size(); v++) {
					if (!parent[v] && doublets(ws[u], ws[v])) {
						parent[v] = u;
						q.push(v);
					}
				}
			}
			if(!parent[zi]) cout << "No solution." << endl;
			else printPath(ai, zi, ws);
		}
	}
	return 0;
}
Advertisements

One thought on “UVA – 10150 – Doublets

  1. Kushol says:

    Time Limit Exceed……………………………………………..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: