网站改版是什么,建筑工程公司有哪些岗位,勒索做钓鱼网站的人,哈尔滨市建设工程信息网官网题目#xff1a;127. 单词接龙 - 力扣#xff08;LeetCode#xff09;
先建立一颗trie树#xff0c;从beginWord开始bfs#xff1b;bfs的过程中#xff0c;对trie树进行dfs寻找“只差一个字母”的其他未遍历到的字符串#xff1b;直到bfs遍历到endWord。
struct Node …题目127. 单词接龙 - 力扣LeetCode
先建立一颗trie树从beginWord开始bfsbfs的过程中对trie树进行dfs寻找“只差一个字母”的其他未遍历到的字符串直到bfs遍历到endWord。
struct Node {Node** c;string str;bool v false;Node() {c (Node**) malloc(26 * sizeof(Node*));memset(c, 0, 26 * sizeof(Node*));}
};
class Solution {
public:void dfs(liststring bfs, listint val, const string s, int path, Node* node, int idx, bool changed) {char c s[idx] - a;Node* t;if (idx s.length() - 1) {if (changed) {t node-c[c];if (t !t-v) {t-v true;bfs.push_back(t-str);val.push_back(path 1);}} else {for (int i 0; i 26; i) {if (i c) continue;t node-c[i];if (t !t-v) {t-v true;bfs.push_back(t-str);val.push_back(path 1);}}}return;}for (int i 0; i 26; i) {if (!node-c[i]) {continue;}if (i c) {dfs(bfs, val, s, path, node-c[i], idx 1, changed);} else if (!changed) {dfs(bfs, val, s, path, node-c[i], idx 1, true);}}}int ladderLength(string beginWord, string endWord, vectorstring wordList) {Node* root new Node;bool hasEndWord false;char c;Node* t;string s;for (int i 0; i wordList.size(); i) {s wordList[i];if (s.compare(endWord) 0) {hasEndWord true;}t root;for (int j 0; j s.length(); j) {c s[j] - a;if (!t-c[c]) {t-c[c] new Node;}t t-c[c];}t-str s;}if (!hasEndWord) {return 0;}liststring bfs;bfs.push_back(beginWord);listint val;val.push_back(1);int path;while (!bfs.empty()) {s bfs.front();bfs.pop_front();path val.front();val.pop_front();
// printf(** %s %d\n, s.data(), path);if (s.compare(endWord) 0) {return path;}dfs(bfs, val, s, path, root, 0, false);}return 0;}
};
