online advertising

## Friday, December 26, 2014

### UVa Problem 417 - Word Index

Problem:

Please find the problem here.

Solution:

The word index is basically the level order of this tree.

BFS with a counter can solve this problem quickly.

Open problem: Can we solve this without going through the sub-trees? Note that the number of all nodes with length 3 starting with a is the set of all size 2 combinations formed with b...z prefixed with a, so the size of that whole a sub-tree can be found quickly using binomial coefficients.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=358

#include "UVa417.h"

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int UVa417()
{
while (true)
{
string s;
cin >> s;
if (cin.eof())
{
break;
}
bool valid = true;
for (unsigned int i = 1; i < s.length(); i++)
{
if (s[i] <= s[i - 1])
{
valid = false;
break;
}
}
if (valid)
{
queue<string> bfs_queue;
bfs_queue.push("");
int count = 0;
while (true)
{
string v = bfs_queue.front();
if (v == s)
{
break;
}
count++;
bfs_queue.pop();
if (v == "")
{
for (char c = 'a'; c <= 'z'; c++)
{
char s[2];
s[0] = c;
s[1] = 0;
bfs_queue.push(s);
}
}
else
{
char last = v[v.length() - 1];
for (char next = last + 1; next <= 'z'; next++)
{
bfs_queue.push(v + next);
}
}
}
cout << count << endl;
}
else
{
cout << 0 << endl;
}
}
return 0;
}

#### 2 comments :

1. Can you please explain the logic ! i solve the same question using loops but i want to do it with BFS !
As i am new to graphs algorithms , please help me with your logic !!

1. Hello Mr. Thakkar, this is being solved by iterating along all the strings uptil the required string but with a queue. The BFS is just for visualisation of what is happening here.