leetcode 127. 单词接龙

题目：127. 单词接龙 - 力扣（LeetCode）

先建立一颗trie树，从beginWord开始bfs；bfs的过程中，对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(list<string>& bfs, list<int>& 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, vector<string>& 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;}list<string> bfs;bfs.push_back(beginWord);list<int> 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;}
};