青岛网站seo推广,自己做淘宝客网站吗,零基础学编程,网站开发项目成本分析之合理性写在前面#xff1a;
今天我们来看一道图论的题#xff0c;这道题目是我做过目前最难与图论联想到的一道题目之一。如果没有提示的话#xff0c;我们很容易往 dp 等解决 array 问题的方向去解决它#xff0c;经过我超过 2个小时的思考我觉得这种方向是没前途的#xff5e…
写在前面
今天我们来看一道图论的题这道题目是我做过目前最难与图论联想到的一道题目之一。如果没有提示的话我们很容易往 dp 等解决 array 问题的方向去解决它经过我超过 2个小时的思考我觉得这种方向是没前途的 那今天就让我们一起来看下这道看起来不像是图论的题我们怎么样巧妙的把它转化为图论中找最小路径的问题并利用 BFS 等经典算法将它解决 题目介绍
题目信息
题目链接https://leetcode.com/problems/word-ladder/description/题目类型GraphBFS题目难度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, vectorstring: semantic, vectorstring 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_mapstring, vectorstring dictStringFormat;unordered_mapstring, bool visited;//BFS to find the answer, return the shortest level we need or 0 if no solutions. int BFSRes(string beginWord, string endWord, vectorstring wordList){queuepairstring, 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(i1);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, vectorstring 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(i1);dictStringFormat[word_semantic].push_back(word);}}//Perform BFS from start to find the shortest path to the end: return BFSRes(beginWord, endWord, wordList);}
};
RuntimeO(M^2 N) M 是每一个字符串的长度N是中间节点字符串的个数SpaceO(M^2 N) M是每一个字符串的长度因为我们对每一个字符串都存储了与他长度相等多的 semantic就是 M*M。同时我们在 visited 和 queue 中存储了 N 个 中间节点
