Write a game Program in C++ called \"Word Laddar\". For example, we can go from

Question

Write a game Program in C++ called "Word Laddar". For example, we can go from HATE to LOVE in four steps, HATE - LATE -LAVE - LOVE, ext... Each intermediate word must exist in the dictionary, and must be four letters. Create your own graph class. Any functions or varaibles can be in the class, as long as it works in main file. Find word laddar by using Breadth first search. Make sure the program is working in C++ IDE.
Data source for 4 letter words in English is below. May write a read file function to go through all the words
http://www.scrabble.org.au/words/fours.htm

Explanation / Answer

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
int ladderLength(std::string beginWord, std::string endWord, std::unordered_set<std::string> &dict) {
if (beginWord == endWord)
return 1;
std::unordered_set<std::string> words1, words2;
words1.insert(beginWord);
words2.insert(endWord);
dict.erase(beginWord);
dict.erase(endWord);
return ladderLengthHelper(words1, words2, dict, 1);
}

private:
int ladderLengthHelper(std::unordered_set<std::string> &words1, std::unordered_set<std::string> &words2, std::unordered_set<std::string> &dict, int level) {
if (words1.empty())
return 0;
if (words1.size() > words2.size())
return ladderLengthHelper(words2, words1, dict, level);
std::unordered_set<std::string> words3;
for (auto it = words1.begin(); it != words1.end(); ++it) {
std::string word = *it;
for (auto ch = word.begin(); ch != word.end(); ++ch) {
char tmp = *ch;
for (*ch = 'a'; *ch <= 'z'; ++(*ch))
if (*ch != tmp)
if (words2.find(word) != words2.end())
return level + 1;
else if (dict.find(word) != dict.end()) {
dict.erase(word);
words3.insert(word);
}
*ch = tmp;
}
}
return ladderLengthHelper(words2, words3, dict, level + 1);
}
};

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.