"Edit distance" UVA programming challenge
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 &amp; 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.