# "Edit distance" UVA programming challenge

I'm trying to solve a programming challenge for fun. The programming challenge is here and my solution for the same can be found here.

It currently causes an exceeded time limit.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int a[25001];

bool is_edit_distance_one(string one, string two) {
if ( one.size() == two.size() ) {
bool found_diff = false;
for ( int i = 0 ; i < one.size(); i++ ) {
if ( found_diff && one[i] != two[i] ) return false;
else if ( one[i] != two[i] ) found_diff = true;
}
return true;
}

else if ( (one.size() - two.size()) == 1 && one.find(two) != string::npos )
return true;
else if ( (two.size() - one.size()) == 1 && two.find(one) != string::npos )
return true;

return false;
}

map<string, bool> generate(string one) {
map<string, bool> edits;
string all_chars = "abcdefghijklmnopqrstuvwxyz";

// Generate all strings by adding another letter
for ( int i = 0; i <= one.size(); i++ ) {
for ( int j = 0; j < all_chars.size(); j++ ) {
// split the string at i
string temp = one.substr(0, i);
temp += all_chars[j];
temp += one.substr(i, one.size()-i);
edits[temp] = true;
}
}

// Generate all strings by deleting a letter
for ( int i = 0; i < one.size(); i++ ) {
string temp = one.substr(0, i);
temp += one.substr(i+1, one.size()-i);
edits[temp] = true;
}

// Generate all strings by changing a letter
for ( int i = 0; i < one.size(); i++ ) {
for ( int j = 0; j < all_chars.size(); j++ ) {
string temp = one.substr(0, i);
temp += all_chars[j];
temp += one.substr(i+1, one.size()-i);
edits[temp] = true;
}
}
return edits;
}

int main() {
string s;
int i = 0;
int l;
vector<string> all;
while ( cin >> s ) {
a[i] = 0;
all.push_back(s);

l = all.size();
for ( int i = 0; i < l-1; i++ ) {
map<string, bool> edits = generate(all[l-1]);
if ( edits[all[i]] ) {
a[l-1] = max(a[i]+1, a[l-1]);
}
}
}
sort(a, a+l);
cout << a[l-1] + 1 << endl;
}


Instead of calculating the edit distance between strings (using is_edit_distance_one), I'm generating a map with all possible edit strings of a string and checking if previous strings are present in it (using the function "generate").

• Are there any implementation level mistakes that I'm making that's slowing it down?
• Any particular data structure I should/should not be using?
• Any other algorithm I could use to speed things up?
• don't use std::strings if you want performance Nov 26, 2013 at 14:58
• it seems you want the levenshtein distance between 2 strings Nov 26, 2013 at 15:03
• The longest ladder! In the sample input I see (just by looking) an 8: fog -> log -> dig -> dog -> fig -> fin -> fine -> wine Nov 27, 2013 at 7:54
• @LokiAstari I think the point is that it should be consecutive words, which is why it's only 5. Nov 27, 2013 at 9:09
• @LokiAstari The sequence is dig → fig → fin → fine → wine. Nov 27, 2013 at 11:14

Generating all possible single-edit variations of a word results in a huge number of possibilities! With a 10-letter word, for example, you could add 26 letters in each of 11 positions (before, after, or between letters), remove any of the 10 letters, or modify any of the 10 letters. That's 26 × 11 + 10 + 25 × 10 = 546 possibilities. On average, you could trim that in half if you only consider words that come lexicographically later than the input word. Still, that's a huge inefficiency — enough to rule out that approach altogether.

Your is_edit_distance_one() should take const string & arguments to avoid copying. The body would be improved if you break down the cases as:

switch (one.size() - two.size()) {
case -1: // Is one is a subsequence of two (not necessarily consecutive)?
case +1: // Is two is a subsequence of one (not necessarily consecutive)?
case 0:  // Check for single-letter difference
default: return false;
}


The challenge with the is_edit_distance_one() approach is that if you apply it naïvely (comparing every pair of words), your running time will be O(n2), where n is the number of words.

One technique to consider is to take the hint that no word exceeds 16 letters. Create a char[25001][16] matrix and fill it with '\0' NULs. You can then treat the NULs just like any other char for the purpose of determining edit distances.

Once you have determined which words are one edit distance apart, the search for the longest stepladder should be similar to the Longest Increasing Subsequence problem.

• @QuentinPradet You haven't understood the problem correctly; please refrain from editing. Nov 27, 2013 at 11:21
• (When I edited I thought I understood it, sorry.) Nov 27, 2013 at 12:58
• But only words in the dictionary are valid. So 546 is you upper bound. Lower bound will be much more constrained. But if your dict is n words. Each word will have (on average) k.n words one edit away (as n increases the probability for more words one edit away increases). So this is a graph search problem with n nodes and k.n^2 edges. You have to find the longest path in the graph (presumably without adding a loop). Nov 27, 2013 at 17:30
• @LokiAstari But generate() was clearly not approaching it as a graph search problem. Nov 27, 2013 at 19:50

when you generate the map you immediately throw it away, this will likely be your biggest slowdown

because the map doesn't change in the for you can cache it:

l = all.size();
map<string, bool> edits = generate(s);
for ( int i = 0; i < l-1; i++ ) {
if ( edits[all[i]] ) {
a[l-1] = max(a[i]+1, a[l-1]);
}
}


going back to using is_edit_distance_one would be better if you fix the bug in it (a remove or add in arbitrary location is seen as false)

• It's a good idea, but nothing says it's indeed the biggest slowdown. The correct algorithm uses the Levenshtein distance, which eliminates the need for generate() anyway. Nov 27, 2013 at 9:16