首页 > 代码库 > Word Ladder
Word Ladder
这题的基本思路很轻易看懂，就是转换成图的中的最短路径问题。我一直出现TLE的错误，原因就在转换过程太复杂。
可以遍历整个表，建立邻接表或者邻接矩阵。问题是这个过程就会是一个o(n^2)的过程。恰恰这道题又一个测试用例的词特别多，于是这个转换过程就行不通了。
办法很简单，就是枚举每个词变化一个字母后可能出现的单词（复杂度：length X 26， length是单词的长度），然后看它在不在词典中。这是个笨办法，但是仔细一算，发现确实比O(n^2)算法要快不少。
int ladderLength(string start, string end, unordered_set<string> &dict){ if (start == end) return 0; unordered_map<string, int> visited; queue<string> qs; qs.push(start); string cur = start; visited.insert(pair<string, int>(start, 1)); while (!qs.empty()){ cur = qs.front(); if (cur == end) break; qs.pop(); for (int i = 0; i < cur.size(); i++){ string newword = cur; for (int j = 0; j < 26; j++){ newword[i] = ‘a‘ + j; if (dict.find(newword) != dict.end() && visited.find(newword) == visited.end()){ visited[newword] = visited[cur] + 1; qs.push(newword); } } } } if (visited.count(end) > 0) return visited[end]; else return 0;}
Word Ladder
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。