Word Ladder

tepyotin2

May 5th, 2025

241

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.08 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
struct Step{
string word;
int count;
};
string a, b;
int n;
unordered_set<string> dict;
queue<Step> q;
unordered_map<string, bool> visited;
int main(){
//freopen("wordladder.in", "r", stdin);
cin >> a >> b >> n;
for(int i=0; i<n; i++){
string s;
cin >> s;
dict.insert(s);
}
q.push({a, 0});
visited[a] = true;
while(!q.empty()){
Step v = q.front();
q.pop();
if(v.word == b){
cout << v.count << '\n';
return 0;
}
for(int i=0; i<26; i++){
string temp = v.word;
for(int j=0; j<v.word.size(); j++){
temp = v.word;
temp[j] = i+'a';
//cout << temp << '\n';
if(dict.find(temp) != dict.end() && visited[temp] == false){
//cout << "HI" << '\n';
visited[temp] = true;
q.push({temp, v.count+1});
}
}
//cout << "============" << '\n';
temp = v.word;
char ap = i+'a';
temp = ap+temp;
if(dict.find(temp) != dict.end() && visited[temp] == false){
//cout << "HI" << '\n';
visited[temp] = true;
q.push({temp, v.count+1});
}
for(int j=0; j<v.word.size(); j++){
temp = v.word;
char ap = i+'a';
string sub1 = temp.substr(0, j+1);
string sub2 = temp.substr(j+1, v.word.size()+1);
temp = sub1+ap+sub2;
//cout << temp << '\n';
//temp.insert(j, ap);
if(dict.find(temp) != dict.end() && visited[temp] == false){
//cout << "HI" << '\n';
visited[temp] = true;
q.push({temp, v.count+1});
}
}
temp = v.word;
ap = i+'a';
temp+=ap;
if(dict.find(temp) != dict.end() && visited[temp] == false){
//cout << "HI" << '\n';
visited[temp] = true;
q.push({temp, v.count+1});
}
}
for(int i=0; i<v.word.size(); i++){
string sub1 = v.word.substr(0, i);
string sub2 = v.word.substr(i+1, v.word.size()+1);
string temp = sub1+sub2;
if(dict.find(temp) != dict.end() && visited[temp] == false){
//cout << "HI" << '\n';
visited[temp] = true;
q.push({temp, v.count+1});
}
}
}
cout << "-1" << '\n';
return 0;
}

Add Comment

Please, Sign In to add comment