1

I received the starter code/algorithm for a word ladder that implements Breadth-first search. The program takes a dictionary of words, but I modified it to take an input file. The algorithm I was given prints the length of the path from a source word to a target word ex: If it takes 4 transformations to reach the target word, it will print 4. I want to print the path itself. ex: If the source word is "TOON" and the source word "PLEA" it should print "TOON -> POON -> POIN -> PLIN -> PLIA -> PLEA"

So far I've tried to add a loop that appends the words in a queue to a vector, then returns the vector, but I am getting an error that I don't understand.

main.cpp:42:18: error: no matching member function for
    call to 'push_back'
transformation.push_back(Q.front());

I have been stumped by this for a couple of days , so any help will be appreciated. I'm fairly new to C++ so forgive me for any errors.

Here is the code

#include<bits/stdc++.h>
#include <iostream>

using namespace std;

// To check if strings differ by exactly one character 
bool nextWord(string & a, string & b) {
  int count = 0; // counts how many differeces there
  int n = a.length();

  // Iterator that loops through all characters and returns false if there is more than one different letter 
  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 the words
struct QItem {
  string word;
};

// Returns length of shortest chain to reach 'target' from 'start' 
// using minimum number of adjacent moves. D is dictionary 
int wordLadder(string & start, string & target, set < string > & D) {
  vector < string > transformation;

  // Create a queue for BFS and insert 'start' as source vertex 
  queue < QItem > Q;
  QItem item = {
    start
  }; // Chain length for start word is 1 
  Q.push(item);
  transformation.push_back(Q.front());

  // 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++) {
      // Proccess the next word according to BFS
      string temp = * it;
      if (nextWord(curr.word, temp)) {
        // Add this word to queue from the dictionary
        item.word = temp;
        Q.push(item);

        // Pop from dictionary so that this word is not repeated
        D.erase(temp);

        // If we reached target 
        if (temp == target) {
          return 0;
        }
      }
    }
  }

  return 0;
}

string start;
string target;

// Driver program 
int main() {
  // make dictionary 
  std::ifstream file("english-words.txt");
  set < string > D;

  copy(istream_iterator < string > (file),
    istream_iterator < string > (),
    inserter(D, D.end()));

  cout << endl;
  cout << "Enter Start Word" << endl;
  cin >> start;
  cout << "Enter Target Word" << endl;
  cin >> target;

  cout << wordLadder(start, target, D);
  return 0;
}
acraig5075
  • 10,588
  • 3
  • 31
  • 50
  • I have also tried to return the queue from the function, which would only return one word, but even as a test that had not worked. – Geni Allaine Dec 18 '19 at 05:41
  • You should take a look at [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h), because you probably don't know what it does. Especially in combination with `using namespace std;` (which is [bad practice](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)) it's almost garantueed to cause some strange errors in larger projects. – Lukas-T Dec 18 '19 at 06:12
  • It was apart of the starter code, I'll change it. – Geni Allaine Dec 18 '19 at 06:22

1 Answers1

3

You're trying to append the wrong object to the vector<string>

Change

transformation.push_back(Q.front());

to

transformation.push_back(Q.front().word);
acraig5075
  • 10,588
  • 3
  • 31
  • 50