Leetcode 每日一题：Word Ladder

写在前面：

今天我们来看一道图论的题，这道题目是我做过目前最难与图论联想到的一道题目之一。如果没有提示的话，我们很容易往 dp 等解决 array 问题的方向去解决它，经过我超过 2个小时的思考我觉得这种方向是没前途的～～ 那今天就让我们一起来看下这道看起来不像是图论的题，我们怎么样巧妙的把它转化为图论中找最小路径的问题并利用 BFS 等经典算法将它解决！

题目介绍：

题目信息：

• 题目链接：https://leetcode.com/problems/word-ladder/description/
• 题目类型：Graph，BFS
• 题目难度：Hard
• 题目来源：Google 高频面试真题

题目问题：

• 给定一个字符串数列，一个 BeginWord，一个EndWord
• 要求从 BeginWord 开始，每次只改变一个字母并且改变后的单词需要在 字符串序列中
• 如果能以这样的方式一步步的将 BeginWord 变成 Endword，则求出最少需要几次变化
• 如果无法完成则返回 0
• 例子：

题目想法：

如何利用只变一个字母的特性：

这道题目的题眼就在于每次只能变化一个字母，并且这个变化的规则是必须按着给定字符串里有的 string 进行变化才可以。同时，他又给定了一个 beginWord 和 一个 endWord，要求通过一次次变化之后，能将 beginWord 变成 endWord

如果将字符串数组里的每一个 “中间字符串” 想象成一个个中间节点，beginWord想成起点，endWord想成终点，他们之间如果只是相差一个字母，则有路径链接，这道题目看起来像什么呢？ --- 没错！就是走迷宫类似的图论问题！ 

图论构造：

有了这个思路，我们尝试用可视化的方法把这道题转化为图论问题。我们有一个起点和一个终点节点，每一个给定的 字符串数列元素 都是一个中间节点，并且起点，终点，中间节点直接，如果两个单词只差一个字母，则他们俩是 “邻居”，并且可以互相访问，可构造的抽象图如下：

Adjacent List 构造：

解决图论问题最关键的算法结构就是 adjacent List 的构造，这关系到我们在遍历图的时候如何前进。这道题目的 adjacent 关系就来源于我们的 “只能变化一个字母”

举例：

hot ----> hat   他们只有中间一个字母变化了，所以他们的单词结构都是 “h * t"

dog -----> log 他们同样有相同的单词结构 “ * og”

我们可以看出，对于一个单词，他的每一个字母替换成 *， 都能形成一种 semantic，也就是单词结构，而如果我们根据相同的单词结构，就能随意的在这些单词之间进行切换：

所以我们的 Adjacent List 的结构为：

<string, vector<string>>:    <semantic, vector<string that have this semantic>>

BFS

当我们将 adjacent List 构造出来以后，我们的图形就完成了。接下来，根据题目特性要寻找最短路径，同时每一条路径都是 unweighted 的，同时要避免出现重复，我们选择 BFS 算法来进行遍历

题目解法：

• 创建 semantic 字典
• 遍历所有 给定中间 字符串
  • 根据每个字符串的每一个 semantic进行遍历插入
• 创建 visited 字典避免重复
• 标准 BFS 解决 beginWord 到 endWord 的最短路径问题
  • 创建的 queue 要带上（当前字符串，当前消耗次数）
  • 如果这次 iterate 能成功，返回 消耗次数 +1
  • 如果失败，且未曾访问过，（新字符串，消耗次数 + 1）入队
• 返回 0， BFS 失败没有结果

题目代码：

class Solution {
public:unordered_map<string, vector<string>> dictStringFormat;unordered_map<string, bool> visited;//BFS to find the answer, return the shortest level we need or 0 if no solutions. int BFSRes(string beginWord, string endWord, vector<string>& wordList){queue<pair<string, int>> q;q.push({beginWord, 1});while(!q.empty()){string currentWord = q.front().first;int currentLevel = q.front().second;q.pop();for(int i = 0; i < currentWord.size(); i++){string semantic = currentWord.substr(0, i) + "*" + currentWord.substr(i+1);for(string similarString: dictStringFormat[semantic]){//if we found the stringif(similarString == endWord){return currentLevel + 1;}//else, determine whether enqueue or not:if(!visited.contains(similarString)){visited[similarString] = true;q.push({similarString, currentLevel + 1});}}}}return 0;}int ladderLength(string beginWord, string endWord, vector<string>& wordList) {int stringLen = beginWord.size();//make a connection for each string with one semantic:for(string word: wordList){for(int i = 0; i < stringLen; i++){string word_semantic = word.substr(0, i) + "*" + word.substr(i+1);dictStringFormat[word_semantic].push_back(word);}}//Perform BFS from start to find the shortest path to the end: return BFSRes(beginWord, endWord, wordList);}
};

• Runtime：O(M^2 + N) M 是每一个字符串的长度，N是中间节点字符串的个数
• Space：O(M^2 + N) M是每一个字符串的长度，因为我们对每一个字符串都存储了与他长度相等多的 semantic，就是 M*M。同时，我们在 visited 和 queue 中存储了 N 个 中间节点