"Edit distance" UVA programming challenge

Question

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?

Answer 1

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(n²), 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.

Answer 2

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)