题目描述
给定一个起始单词,一个目标单词与一个备选字典,通过以下规则将起始单词变到目标单词去:
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
求最短变化步数。
思路
看到最短步数,首先想到BFS。但使用BFS的前提是有一个可以用来搜索的图或者树,于是思维转向如何建立图/树。
思路还是很清晰的:任何两个只差一个字母的单词之间可以连成一条无向边,所有的边共同构成整张单词图。建成图后再判断endWord是否在图中就行了。真正复杂的地方在实现。
单个的字符串并不好节点化,我们可以把每个单词映射为一个id值,然后用一个int的邻接矩阵来存储整个词图。
对于添加边的操作,朴素思路枚举每一对单词,判断它们之间是否可以存在一条边,如果是,则将其加入词图,但这样显然太慢了。
可以考虑构造间接节点。假设当前单词为hit,那么显然地,_it、h_t、hi_三个长相的单词都可以与hit连成一条边。那么我们只需要构造出这三个间接节点,然后将当前单词连在间接节点上就行了。不难得知,每一个可以与hit连边的单词都一定会连向这三个间接节点。
值得注意的是,这样的操作虽然节省了时间,但人为的增加了一些“不需要的边”。假设有两个相邻单词,他们原来可以直达彼此,现在需要通过间接节点来访问,所以说真实的步数应该等于当前步数/2。又因为初始化时会将beginWord也加入词图,所以最后的总步数还得额外的+1。
代码
class Solution { public: unordered_map<string, int> wordId; vector<vector<int>> mp; int idNum = 0; void addWord(string& str) { if(!wordId.count(str)) { wordId[str] = idNum++; mp.emplace_back(); } } void addEdge(string& str) { addWord(str); int idu = wordId[str]; for(char& ch : str) { char tmp = ch; ch = '*'; addWord(str); int idv = wordId[str]; mp[idu].push_back(idv); mp[idv].push_back(idu); ch = tmp; } } int ladderLength(string beginWord, string endWord, vector<string>& wordList) { for(string& str : wordList) { addEdge(str); }addEdge(beginWord); if(!wordId.count(endWord)) return 0; vector<int> dis(idNum, INT_MAX); int beginId = wordId[beginWord], endId = wordId[endWord]; dis[beginId] = 0; queue<int> que; que.push(beginId); while(!que.empty()) { int now = que.front();que.pop(); if(now == endId) { return dis[endId] / 2 + 1; } for(int& it : mp[now]) { if(dis[it] == INT_MAX) { dis[it] = dis[now] + 1; que.push(it); } } } return 0; } };
评论
还没有任何评论,你来说两句吧!