-
Notifications
You must be signed in to change notification settings - Fork 0
/
proj.cpp
71 lines (59 loc) · 1.68 KB
/
proj.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include "proj.hpp"
#include "Wordset.hpp"
#include <iostream>
#include <set>
#include <sstream>
#include <map>
#include <stack>
#include <queue>
void loadWordsIntoTable(WordSet & words, std::istream & in)
{
std::string line, word;
std::stringstream ss;
while( getline(in, line) )
{
ss.clear();
ss << line;
while( ss >> word )
{
words.insert( word );
}
}
}
// returns path from s1 to s2
std::string convert(std::string s1, std::string s2, const WordSet & words)
{
std::queue<std::string> q;
std::map<std::string, std::string> mappings;
q.push(s1);
while(!q.empty()) { //loops until q is empty or break occurs
std::string word = q.front();
q.pop();
if (word == s2) { break; } //if s2 is reached
for (int i = 0; i < word.length(); i++) { //loop through every letter in word
for (int j = 0; j < 26; j++) { //loop through every possible letter in alphabet
std::string tempWord = word;
tempWord[i] = j + 'a'; //new word (1 sub away from word)
if (tempWord != word && words.contains(tempWord) && mappings.count(tempWord) == 0) {
q.push(tempWord);
mappings.insert(std::pair<std::string, std::string> (tempWord, word));
}
}
}
}
std::stack<std::string> conversion;
std::string key = s2;
// go through map, going from s2 to s1
while(true) {
conversion.push(key);
key = mappings.at(key);
if (key == s1) break;
}
std::string result = s1;
while(!conversion.empty()) {
std::string temp = conversion.top();
result += " --> " + temp;
conversion.pop();
}
return result;
}