帮我用cpp写一个能找到并显示最短单词阶梯的程序
时间: 2024-05-15 09:17:10 浏览: 7
当然,我很愿意帮你写一个能找到并显示最短单词阶梯的程序!以下是一个简单的 C++ 程序,可以实现该功能。
```
#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
using namespace std;
bool is_adjacent(string& s1, string& s2) {
int count = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1[i] != s2[i]) count++;
if (count > 1) return false;
}
return count == 1;
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
vector<vector<string>> res;
queue<vector<string>> q;
q.push({beginWord});
bool found = false;
while (!q.empty()) {
int size = q.size();
unordered_set<string> visited;
for (int i = 0; i < size; i++) {
vector<string> path = q.front();
q.pop();
string word = path.back();
if (word == endWord) {
found = true;
res.push_back(path);
} else {
for (int j = 0; j < word.length(); j++) {
char ch = word[j];
for (int k = 0; k < 26; k++) {
word[j] = 'a' + k;
if (dict.count(word) && !visited.count(word)) {
vector<string> new_path = path;
new_path.push_back(word);
q.push(new_path);
}
}
word[j] = ch;
}
}
}
for (auto& word : visited) dict.erase(word);
if (found) break;
}
return res;
}
int main() {
string beginWord = "hit";
string endWord = "cog";
vector<string> wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
vector<vector<string>> res = findLadders(beginWord, endWord, wordList);
for (auto& path : res) {
for (auto& word : path) {
cout << word << " ";
}
cout << endl;
}
return 0;
}
```
如上所示,该程序使用 BFS 算法搜索从开始单词到结束单词的最短单词阶梯。函数 `findLadders()` 采用了一些超时优化技巧,例如每次遍历时将已访问单词从集合中删除,以便加速搜索过程。
如果您有任何疑问,或者对程序的优化有任何建议,都可以随时与我进行对话!