题目描述
Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]
As one shortest transformation is “hit” -“hot” -“dot” -“dog” -“cog”,
return its length 5.
解题分析
此题总体思路是广度优先BFS搜索，利用队列可进行，但是几次尝试都超时：
首先我利用关系矩阵表示图关系，这样TLE，分析也可看到N*N的复杂度。 后来利用邻接表方式表示，注意到这里小写字母只有26个，又题目说明字符串长度相同，则边的数目最大L*26，邻接表遍历搜索就很快N*L*26，但是建立邻接表的过程还是N*N，依然TLE，尝试发现对于大数据邻接表建立的过程中就超时了。 最后依然是利用边数目有限的思想，由一个单词直接去生成可达单词然后判断是否在字典中，这样就不需要生成邻接表了，这里我由于最初数据处理使用了Linkedlist，使得在判断是否属于候选集的时候也就是contain object的时候费时，TLE，最后使用set结构，终于ac。 回顾很多知识点，BFS和队列，矩阵和邻接表，java的 set 和 collection， java的queue接口一般由linkedlist实现
详细代码
public class Solution {
public int ladderLength(String beginWord, String endWord, Set
wordDict) { wordDict.add(endWord); wordDict.add(endWord); Queue
queue = new LinkedList
(); queue.add(new NodeString(beginWord, 1)); wordDict.remove(beginWord); while(!queue.isEmpty()) { NodeString current = queue.poll(); if(current.string.equals(endWord)) { return current.deep; } else { String tmp = current.string;//取点 找临街的表，这里借助最大固定数目的变数来计算而非常规利用矩阵 for(int i=0;i