Строковые векторы C ++

Question

Я пытаюсь создать дерево данных из строк, которые расширены как минимум на 1 букву, которая доступна из текущего начального слова. Мое начальное слово в этом случае Dog и конечное слово, которое я хочу для этого случая, может быть, кошка. Я должен проверить, что слово из словаря имеет тот же размер и не уже в словах вектора, а также, что если это только 1 разность букв. Ниже я уже пытался реализовать этот тип мышления, но я думаю, что упускаю что-то важноеТо, что мне нужна помощь в поиске или, возможно, добавлении в мой код.

#include <iostream>
#include <bits/stdc++.h>
#include <cctype>       // For the letter checking functions
#include <fstream>      // For file input
#include <vector>       // For the use of vectors
#include <cstdlib>      // For exit and abs
using namespace std;



int main(){

vector<string> dictionary;
vector<string> words;
string startWord = "dog";
string endWord = "cat";

dictionary.push_back("dog");
dictionary.push_back("bog");
dictionary.push_back("cog");
dictionary.push_back("fog");
dictionary.push_back("cat");


 words.push_back(startWord);
                int counter = 0;
                int countline = 0;
                while( counter < words.size() ){
                    cout << words[counter] << ":   ";
                    for(int j = 0; j < dictionary.size(); j++){
                        for(int l = 0; l < startWord.size(); l++){
                            for(int k = 0; k < dictionary.at(j).length(); k++){
                                if(dictionary.at(j)[k] == startWord[k]){
                                    counter++;
                                    if(counter == 1){
                                        countline++;
                                        words.push_back(dictionary[l]);
                                        cout << words[l]<< endl;
                                        cout << " The succeded word is "<< words[l] << endl;
                                    }
                                }
                            }
                        }
                    }
                } // ends while

Я предоставил только некоторые слова в своем Словаре, но на самом деле у меня есть много фактического кода, который имеет длину 3 ив фактическом словаре (Webster). Я добавил этих немногих только ради общего понимания того, что мне нужно.

Пример вывода, который я пытаюсь достичь, должен быть примерно таким ...

0. dog:   1:bog 2:cog 3:fog 4:gog 5:hog 6:jog 7:log 8:mog 9:nog 10:rog 11:sog 12:tog 13:vog 14:wog 15:dag 16:deg 17:dig 18:dug 19:dob 20
:doc 21:dod 22:doe 23:dol 24:dom 25:don 26:dop 27:dor 28:dos 29:dot 30:dow
1. bog:   31:bag 32:beg 33:big 34:bug 35:boa 36:bob 37:bod 38:bom 39:bon 40:boo 41:bop 42:bor 43:bos 44:bot 45:bow 46:boy
2. cog:   47:cag 48:cig 49:cob 50:cod 51:coe 52:col 53:con 54:coo 55:cop 56:cor 57:cos 58:cot 59:cow 60:cox 61:coy 62:coz
3. fog:   63:fag 64:fig 65:fob 66:fod 67:foe 68:fon 69:foo 70:fop 71:for 72:fot 73:fou 74:fow 75:fox 76:foy
4. gog:   77:gag 78:gig 79:goa 80:gob 81:god 82:goi 83:gol 84:gon 85:goo 86:gor 87:gos 88:got 89:goy
5. hog:   90:hag 91:hug 92:hob 93:hod 94:hoe 95:hoi 96:hon 97:hop 98:hot 99:how 100:hox 101:hoy
6. jog:   102:jag 103:jig 104:jug 105:job 106:joe 107:jon 108:jos 109:jot 110:jow 111:joy
7. log:   112:lag 113:leg 114:lug 115:loa 116:lob 117:lod 118:lof 119:loo 120:lop 121:lot 122:lou 123:low 124:lox 125:loy
8. mog:   126:mag 127:meg 128:mig 129:mug 130:mob 131:mod 132:moe 133:moi 134:mon 135:moo 136:mop 137:mor 138:mot 139:mou 140:mow 141:mo
y
9. nog:   142:nag 143:nig 144:noa 145:nob 146:nod 147:non 148:nor 149:not 150:nou 151:now 152:noy
10. rog:   153:rag 154:reg 155:rig 156:rug 157:rob 158:roc 159:rod 160:roe 161:roi 162:rok 163:ron 164:rot 165:row 166:rox 167:roy
11. sog:   168:sag 169:seg 170:sig 171:sob 172:soc 173:sod 174:soe 175:soh 176:sok 177:sol 178:son 179:sop 180:sot 181:sou 182:sov 183:s
ow 184:soy
12. tog:   185:tag 186:teg 187:tig 188:tug 189:tyg 190:toa 191:tod 192:toe 193:toi 194:tol 195:tom 196:ton 197:too 198:top 199:tor 200:t
ot 201:tou 202:tow 203:tox 204:toy
13. vog:   205:vag 206:vug 207:vod 208:voe 209:vol 210:vow
14. wog:   211:wag 212:wig 213:wob 214:wod 215:woe 216:won 217:woo 218:wop 219:wot 220:wow 221:woy
15. dag:   222:zag 223:dab 224:dad 225:dae 226:dah 227:dak 228:dal 229:dam 230:dan 231:dao 232:dap 233:dar 234:das 235:daw 236:day
16. deg:   237:keg 238:peg 239:deb 240:dee 241:del 242:den 243:dev 244:dew 245:dey
17. dig:   246:pig 247:zig 248:dib 249:did 250:die 251:dim 252:din 253:dip 254:dis 255:dit 256:div
18. dug:   257:pug 258:dub 259:dud 260:due 261:dum 262:dun 263:duo 264:dup 265:dux
19. dob:   266:kob 267:pob
20. doc:
21. dod:   268:pod
22. doe:   269:poe 270:yoe 271:dye
23. dol:   272:kol 273:pol
24. dom:   274:pom 275:yom
25. don:   276:eon 277:ion 278:kon 279:pon 280:yon
26. dop:   281:kop 282:pop
27. dor:   283:kor 284:yor
28. dos:   285:kos
29. dot:   286:pot 287:yot
30. dow:   288:pow 289:yow
31. bag:   290:baa 291:bab 292:bac 293:bad 294:bae 295:bah 296:bal 297:bam 298:ban 299:bap 300:bar 301:bas 302:bat 303:baw 304:bay
32. beg:   305:bea 306:bed 307:bee 308:bel 309:ben 310:ber 311:bes 312:bet 313:bey
33. big:   314:bib 315:bid 316:bim 317:bin 318:bis 319:bit 320:biz
34. bug:   321:bub 322:bud 323:bum 324:bun 325:bur 326:bus 327:but 328:buy
35. boa:   329:koa 330:poa 331:zoa 332:bra
36. bob:
37. bod:
38. bom:
39. bon:
40. boo:   333:zoo 334:blo
41. bop:
42. bor:
43. bos:
44. bot:
45. bow:
46. boy:   335:poy 336:yoy
47. cag:   337:cab 338:cad 339:cal 340:cam 341:can 342:cap 343:car 344:cat

Answer 1

Чтобы избежать бесконечного цикла, вам нужно запомнить слова, которые вы уже видели. В следующем примере кода я использую unordered_set<string> для этого (добавьте #include <unordered_set>.

Тогда код может выглядеть следующим образом:

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

using namespace std;

int main() {
    vector<string> dictionary;
    vector<pair<string, int>> words; //stores (word, predecessor)
    string startWord = "dog";
    string endWord = "cat";

    unordered_set<string> seenWords;

    dictionary.push_back("dog");
    dictionary.push_back("bog");
    dictionary.push_back("cog");
    dictionary.push_back("fog");
    dictionary.push_back("cat");
    dictionary.push_back("bag");
    dictionary.push_back("beg");
    dictionary.push_back("bet");
    dictionary.push_back("bat");


    words.emplace_back(startWord, -1);
    seenWords.insert(startWord);

    bool found = false;

    //Try all new words as reference words
    for(int i = 0; i < words.size() && !found; ++i) {       
        //we look for words that we can generate from words[i]
        cout << i << " " << words[i].first << ":   ";

        //try all the words from the dictionary
        for (int j = 0; j < dictionary.size(); j++) {
            string& candidate = dictionary[j];
            //check if candidate can be generated from reference

            //count the different characters
            int differentCharacters = 0;
            for (int pos = 0; pos < words[i].first.size(); ++pos)
            {
                if (candidate[pos] != words[i].first[pos])
                    ++differentCharacters;
            }
            if (differentCharacters == 1 && seenWords.find(candidate) == seenWords.end()) {
                //yes, we can generate this candidate from word[i] and we haven't seen the word before
                cout << "(" << words.size() << ")" << candidate << " ";                         

                words.emplace_back(candidate, i);
                seenWords.insert(candidate);

                if (candidate == endWord) {
                    found = true;
                    cout << "Found endword";
                    break;
                }
            }           
        }
        cout << endl;
    }

    if (found) {
        //traverse the word path from the end word back to the start word
        int i = words.size() - 1;
        stack<string> wordPath;
        while (i != -1) {
            //push the current word onto a stack
            wordPath.push(words[i].first);
            //go to the previous word
            i = words[i].second;
        }

        //now retrieve the words from the stack and print them in reverse order
        cout << "Word path:" << endl;
        while (!wordPath.empty()) {
            cout << wordPath.top() << " ";
            wordPath.pop();
        }
        cout << endl;
    }

    return EXIT_SUCCESS;
}

Что дает нам:

0 dog:   (1)bog (2)cog (3)fog
1 bog:   (4)bag (5)beg
2 cog:
3 fog:
4 bag:   (6)bat
5 beg:   (7)bet
6 bat:   (8)cat Found endword
Word path:
dog bog bag bat cat

Живая версия может быть найдена здесь