Shortest path to transform one word into another

user_127139 0
Viewed 31148

For a Data Structures project, I must find the shortest path between two words (like "cat" and "dog"), changing only one letter at a time. We are given a Scrabble word list to use in finding our path. For example:

cat -> bat -> bet -> bot -> bog -> dog

I've solved the problem using a breadth first search, but am seeking something better (I represented the dictionary with a trie).

Please give me some ideas for a more efficient method (in terms of speed and memory). Something ridiculous and/or challenging is preferred.

I asked one of my friends (he's a junior) and he said that there is no efficient solution to this problem. He said I would learn why when I took the algorithms course. Any comments on that?

We must move from word to word. We cannot go cat -> dat -> dag -> dog. We also have to print out the traversal.

hamming-distance shortest-path edit-distance algorithm
9 Answers
bool isadjacent(string& a, string& b)
{
  int count = 0;  // to store count of differences
  int n = a.length();

  // Iterate through all characters and return false
  // if there are more than one mismatching characters
  for (int i = 0; i < n; i++)
  {
    if (a[i] != b[i]) count++;
    if (count > 1) return false;
  }
  return count == 1 ? true : false;
}

// A queue item to store word and minimum chain length // to reach the word.

struct QItem
{
  string word;
  int len;
};

// Returns length of shortest chain to reach 'target' from 'start' // using minimum number of adjacent moves. D is dictionary

int shortestChainLen(string& start, string& target, set<string> &D)
{
  // Create a queue for BFS and insert 'start' as source vertex
  queue<QItem> Q;
  QItem item = {start, 1};  // Chain length for start word is 1
  Q.push(item);

  // While queue is not empty
  while (!Q.empty())
  {
    // Take the front word
    QItem curr = Q.front();
    Q.pop();

    // Go through all words of dictionary
    for (set<string>::iterator it = D.begin(); it != D.end(); it++)
    {
        // Process a dictionary word if it is adjacent to current
        // word (or vertex) of BFS
        string temp = *it;
        if (isadjacent(curr.word, temp))
        {
            // Add the dictionary word to Q
            item.word = temp;
            item.len = curr.len + 1;
            Q.push(item);

            // Remove from dictionary so that this word is not
            // processed again.  This is like marking visited
            D.erase(temp);

            // If we reached target
            if (temp == target)
              return item.len;
        }
    }
  }
  return 0;
}

// Driver program
int main()
{
  // make dictionary
  set<string> D;
  D.insert("poon");
  D.insert("plee");
  D.insert("same");
  D.insert("poie");
  D.insert("plie");
  D.insert("poin");
  D.insert("plea");
  string start = "toon";
  string target = "plea";
  cout << "Length of shortest chain is: "
       << shortestChainLen(start, target, D); 
  return 0; 
}

Copied from: https://www.geeksforgeeks.org/word-ladder-length-of-shortest-chain-to-reach-a-target-word/

user_26519810
Related