Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionaryFor example,
Given:
start = “hit”
end = “cog”
dict = [“hot”,”dot”,”dog”,”lot”,”log”]Return
[ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]
public class Solution {
public List> findLadders(String start, String end, Set dict) {
List> resultLists = new ArrayList<>();//結果
dict.add(start);//頭部加入
dict.add(end);//尾部加入
Queue queue = new LinkedList();
queue.add(new NodeForLadder(start, 1, null));//入隊 深度1 父節點null
Set visitedPerDeepList = new HashSet();//記錄當前層次遍歷過的節點
int currentDeep = 1; //初始化當前深度1
Boolean hasFound = false;
while(!queue.isEmpty())
{
NodeForLadder current = queue.poll();
if(current.deep != currentDeep)
{
//已經進入到下一個層次,將原先層次所有的節點先刪除掉
dict.removeAll(visitedPerDeepList);
//更新層次信息
currentDeep = current.deep;
if(hasFound)
{
break;//已經找到最短路徑,再次更新層次進入下一層,說明上一層遍歷完畢,最短路徑們都已走過
}
visitedPerDeepList.clear();//已經遍歷的層次節點清空
}
visitedPerDeepList.add(current.string);//加入遍歷過的層次節點
if(current.string.equals(end))
{
//找到最短路徑 添加
resultLists.add(findLadderPath(current));
hasFound = true; // 抵達最短層
}
else
{
//取點 找臨街的表,這裡借助最大固定數目的變數來計算而非常規利用矩陣
String tmp = current.string;
//首先判斷是否還有此點,以為層次更新時會刪除上一層節點,這裡排除回路的情況
if(!dict.contains(tmp))
{
continue;
}
for(int i=0;i findLadderPath(NodeForLadder n)
{
List pathList = new LinkedList<>();
while(n != null)
{
pathList.add(0, n.string);
n = n.parent;
}
return pathList;
}
}
代碼中的注釋就是按照上述思路來的,此題屬於AC率較低的(前五),尤其適用java來做的話對算法的要求更高,需要熟悉java集合的使用,比如頭結點插入操作LinkedList效率高於ArrayList,判斷集合中是否含有某一元素的話Set(O(1))效率高於LinkedList(O(n)),許多細節需要注意,總體的思路要正確(利用26小寫字母)以及具體編碼實現(集合選取,前驅記錄,visitedPerDeepList記錄等等)