首页 > 代码库 > [Leetcode][JAVA] Word Ladder II

[Leetcode][JAVA] Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [    ["hit","hot","dot","dog","cog"],    ["hit","hot","lot","log","cog"]  ]

 

Note:

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

难度挺高的一题。沿用Word Ladder I的思路,此题本质也是图的遍历问题,求的是从给定起点到给定终点之间的所有最短路径。

Word Ladder I 中,找到一条合法路径即返回。然而此题中找到一条之后还需要进行讨论,问题就变复杂了,因为广度优先遍历中之前的节点都已经出队列没法再获取到。

所以,沿用Word Ladder I中的思想,不仅记录每个结点距离start的距离,而且用List记录这个到达这个节点的所有最短路径上的前驱结点。举个例子:

 

 

6的List应当为 2 和 3, 因为5 不是最短路径上的点。

这里采用HashMap去处理结点和List的映射关系。

这样在进行广度优先遍历过程中,会有以下几种情况:

1. 相邻结点新结点,那么新结点入队列;建立新结点的List和,把当前结点加入到新结点的List中;记录新结点的最短路径长度为当前结点的最短路径长度L+1

2. 相邻结点在队列中(例如上图结点3出队列时,6还在队列中)且相邻结点的最短路径长度=当前结点最短路径长度+1,那么说明是另一条最短路径,只需要把当前结点加入到相邻结点的List中。

3. 相邻结点在队列中且相邻结点的最短路径长度<当前结点最短路径长度+1,说明这条不是最短路径,那么什么也不做,当前结点默默出队列。

这样我们可以得到从start到end的若干条链,从end开始逆向使用回溯法记录所有的链上的结点即可。

代码如下:

 1     HashMap<String, ArrayList<String>> nodeSet = new HashMap<String, ArrayList<String>>(); 2     public List<List<String>> findLadders(String start, String end, Set<String> dict) { 3         List<List<String>> re = new ArrayList<List<String>>(); 4         Queue<String> q = new LinkedList<String>(); 5         HashSet<String> hs = new HashSet<String>(); 6         HashMap<String, Integer> dist = new HashMap<String, Integer>(); 7         q.add(start); 8         nodeSet.put(start, new ArrayList<String>()); 9         nodeSet.put(end, new ArrayList<String>());10         dist.put(start, 1);11         12         while(!q.isEmpty()) {13             String temp = q.poll();14             int l = dist.get(temp);15             hs.add(temp);16             for(int i=0;i<temp.length();i++) {17                 for(char c=‘a‘;c<=‘z‘;c++) {18                     if(temp.charAt(i)==c)19                         continue;20                     StringBuilder sb = new StringBuilder(temp);21                     sb.setCharAt(i,c);22                     String next = sb.toString();23                     if(next.equals(end)) {24                         if(!dist.containsKey(end)) {25                             dist.put(end,l+1);26                             nodeSet.get(end).add(temp);27                         }28                         else if(dist.get(end)==l+1)29                             nodeSet.get(end).add(temp);30                     }31                     else if(dict.contains(next) && !hs.contains(next)) {32                         if(!dist.containsKey(next)) {33                             q.add(next);34                             dist.put(next, l+1);35                             ArrayList<String> arr = new ArrayList<String>();36                             arr.add(temp);37                             nodeSet.put(next, arr);38                         } else if(dist.get(next)==l+1)39                             nodeSet.get(next).add(temp);40                     }41                 }42             }43         }44         List<String> path = new ArrayList<String>();45         path.add(end);46         collect(start,re,path,nodeSet.get(end));47         return re;48     }49     public void collect(String start, List<List<String>> re, List<String> path, ArrayList<String> prevNodes)50     {51         for(int i=0;i<prevNodes.size();i++)52         {53             path.add(0,prevNodes.get(i));54             if(prevNodes.get(i).equals(start)) {55                 List<String> pathCopy = new ArrayList<String>(path);56                 re.add(pathCopy);57             }58             else59                 collect(start,re,path,nodeSet.get(prevNodes.get(i)));60             path.remove(0);61         }62     }

 

 

[Leetcode][JAVA] Word Ladder II