LeetCode126. Word Ladder

题目

题目给定两个单词（start和end）和由一组单词组成的词典，要求找到从start到end所有的变形序列，满足：

每次只能改变一个字母；变形序列中的所有单词必须在词典中存在

举例来说，

start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"]

一种可能的变换序列是”hit” -> “hot” -> “dot” -> “dog” -> “cog”，所以返回

5

分析

已经通过了这题的升级版126 Word Ladder II，顺手做一下这一题，同样，题目给出了一些节点和构成图的方法，相当于给出了一个图，127题只需要求出最短路的长度，事实上并不用求出任何一条最短路，比126题简单很多。

无权图其实就是权重为1的有权图，求最短长度，可以直接套Dijkstra算法，敲出来就好；另外，像上次分析的那样，Dijkstra算法就是一种特殊的BFS，本题直接用BFS就可以解决，因为BFS过程在一个图的每一层进行，层是按远离start的方向，以距离距离区分，距离相等的顶点是一层，只要知道end点是在那一层就知道最短距离，用最传统的BFS稍加修改就可以做到。

实现

在具体实现上，我沿用了127中的做法，选择先把整个图构建出来，而且依然使用了索引的方式，虽然在本题中，这样做可能不太理性，但是能利用已有代码，工作量小一些。

本题如果直接套Dijkstra算法，就没什么好说的，完全不用修改就能通过，如果用数组实现，复杂度O(|V|^2)。

如果使用BFS，则需要记录end点在哪一层，与126题不同，127题无需访问队列中的内容，不必用两个队列，可以在访问每一层开始的时候先记录当前队列的长度，仅访问该长度次，之后自然就转而访问下一层，距离值就可以++，当访问到end时，返回距离就可以了。BFS的复杂度为O(|V|+|E|)，考虑到|E|一般比|V|大，但不会大过|V|^2，因为即使每一个单词都可以一次变为其他单词，那么|E|=|V|*（|V|-1），所以这里用BFS的做法总是优于套Dijkstra算法。

代码

#include <iostream> #include <string> #include <cassert> #include <cstdlib> #include <vector> #include <unordered_map> #include <unordered_set> using namespace std; template<class Vex> class Graph { public: vector<unordered_set<int> > adj; vector<Vex> VLookup; unordered_map<Vex, int> VIndexLookup; int getVexIndex(const Vex& v) const { assert(VIndexLookup.count(v) != 0); return VIndexLookup.at(v); } inline unsigned int size() const { return VLookup.size(); } bool addVex(const Vex& v) { if (VIndexLookup.count(v) != 0) return false; VIndexLookup[v] = VLookup.size(); VLookup.push_back(v); adj.push_back(unordered_set<int>()); return true; } void addEdge(const Vex& start, const Vex& end) { const int startIndex = getVexIndex(start); const int endIndex = getVexIndex(end); adj[startIndex].insert(endIndex); } void print() const { for (unsigned int u = 0; u < size(); ++u) { cout << VLookup[u] << ": "; for (const int v : adj[u]) cout << VLookup[v] << " "; cout << endl; } } }; class Solution { #define INF_WEIGHT (0x0fffffff) int Dijsktra(const int startIndex, const int endIndex, const Graph<string>& G) { unordered_set<int> unvisited; for (int i = 0; i < int(G.size()); ++i) unvisited.insert(i); vector<int> dist(G.size(), INF_WEIGHT); int minDist = INF_WEIGHT; int minDistIdx = -1; dist[startIndex] = 0; while (!unvisited.empty()) { minDist = INF_WEIGHT; for (const int i : unvisited) { if (minDist >= dist[i]) { minDist = dist[i]; minDistIdx = i; } } unvisited.erase(minDistIdx); for (const int v : G.adj[minDistIdx]) { if (dist[v] > dist[minDistIdx] + 1) dist[v] = dist[minDistIdx] + 1; } } return dist[endIndex] == INF_WEIGHT ? 0 : dist[endIndex] + 1; } int BFS(const int startIndex, const int endIndex, const Graph<string>& G) { vector<bool> visited(G.size(), false); queue<int> bfs_queue; int dist = 0; unsigned int size; bfs_queue.push(startIndex); visited[startIndex] = true; while (!bfs_queue.empty()) { size = bfs_queue.size(); dist++; while (size--) { const int u = bfs_queue.front(); /* visit bfs_queue.front()*/ if (u == endIndex) return dist; for (const int v : G.adj[u]) { if (!visited[v]) { bfs_queue.push(v); visited[v] = true; } } bfs_queue.pop(); } } return 0; } public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { if (find(wordList.begin(), wordList.end(), endWord) == wordList.end()) return 0; Graph<string> G; G.addVex(beginWord); for (const string& w : wordList) G.addVex(w); for (unsigned int i = 0; i < G.VLookup.size(); ++i) { for (unsigned int j = i + 1; j < G.VLookup.size(); ++j) { const string& w1 = G.VLookup[i]; const string& w2 = G.VLookup[j]; int dist = 0; for (unsigned int k = 0; k < w1.size(); ++k) if (w1[k] != w2[k]) dist++; if (dist == 1) { G.addEdge(w1, w2); G.addEdge(w2, w1); } } } // G.print(); return BFS(G.getVexIndex(beginWord), G.getVexIndex(endWord), G); } }; int main(int argc, char const *argv[]) { Solution s; string beginWord = "qa"; string endWord = "sq"; // 5 vector<string> wordList({ "si", "go", "se", "cm", "so", "ph", "mt", "db", "mb", "sb", "kr", "ln", "tm", "le", "av", "sm", "ar", "ci", "ca", "br", "ti", "ba", "to", "ra", "fa", "yo", "ow", "sn", "ya", "cr", "po", "fe", "ho", "ma", "re", "or", "rn", "au", "ur", "rh", "sr", "tc", "lt", "lo", "as", "fr", "nb", "yb", "if", "pb", "ge", "th", "pm", "rb", "sh", "co", "ga", "li", "ha", "hz", "no", "bi", "di", "hi", "qa", "pi", "os", "uh", "wm", "an", "me", "mo", "na", "la", "st", "er", "sc", "ne", "mn", "mi", "am", "ex", "pt", "io", "be", "fm", "ta", "tb", "ni", "mr", "pa", "he", "lr", "sq", "ye" }); cout << s.ladderLength(beginWord, endWord, wordList) << endl; system("pause"); return 0; }

代码包含测试使用的main函数和打印函数，还有一个使用template编写的Graph辅助类，用于构建无权图，方法上包含了Dijsktra和BFS两种，都可以通过题目。