IT工程師數位筆記本

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time

Each intermediate word must exist in the word list

For example,

Given:

beginWord = “hit”

endWord = “cog”

wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Return

[

[“hit”,”hot”,”dot”,”dog”,”cog”],

[“hit”,”hot”,”lot”,”log”,”cog”]

]

//*******************************************************************// NOTE: please read the 'More Info' tab to the right for shortcuts.//*******************************************************************import java.lang.Math; // headers MUST be above the first classimport java.util.*;// one class needs to have a main() methodpublic class Solution {   public List<List<String>> findLadders(String start, String end, Set<String> dict) {         List<List<String>> res = new ArrayList<List<String>>();            HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<String, ArrayList<String>>();// Neighbors for every node   HashMap<String, Integer> distance = new HashMap<String, Integer>();// Distance of every node from the start node   ArrayList<String> solution = new ArrayList<String>();   dict.add(end);             bfs(start, end, dict, nodeNeighbors, distance);                    dfs(start, end, dict, nodeNeighbors, distance, solution, res);     System.out.println(res);   return res;}// BFS: Trace every node's distance from the start node (level by level).private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) {  for (String str : dict)      nodeNeighbors.put(str, new ArrayList<String>());  nodeNeighbors.put(start, new ArrayList<String>());  Queue<String> queue = new LinkedList<String>();  queue.offer(start);  distance.put(start, 0);  while (!queue.isEmpty()) {      int count = queue.size();      boolean foundEnd = false;      for (int i = 0; i < count; i++) {          String cur = queue.poll();          int curDistance = distance.get(cur);                          ArrayList<String> neighbors = getNeighbors(cur, dict);//        System.out.println(neighbors+","+cur);          System.out.println("distance=="+distance);            System.out.println(nodeNeighbors);          for (String neighbor : neighbors) {              nodeNeighbors.get(cur).add(neighbor);              if (!distance.containsKey(neighbor)) {// Check if visited              //  System.out.println("false "+neighbor);                  distance.put(neighbor, curDistance + 1);                  if (end.equals(neighbor))// Found the shortest path                      foundEnd = true;                  else                      queue.offer(neighbor);                  }              }          }          if (foundEnd)              break;      }  }// Find all next level nodes.    private ArrayList<String> getNeighbors(String node, Set<String> dict) {  ArrayList<String> res = new ArrayList<String>();  char chs[] = node.toCharArray();  //System.out.println(node);  for (char ch ='a'; ch <= 'z'; ch++) {      for (int i = 0; i < chs.length; i++) {          if (chs[i] == ch) continue;          char old_ch = chs[i];          chs[i] = ch;          //System.out.println(String.valueOf(chs));          if (dict.contains(String.valueOf(chs))) {              res.add(String.valueOf(chs));          }          chs[i] = old_ch;      }  }  return res;}// DFS: output all paths with the shortest distance.private void dfs(String cur, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) {           solution.add(cur);   if (end.equals(cur)) {           res.add(new ArrayList<String>(solution));       }       else {           for (String next : nodeNeighbors.get(cur)) {                           if (distance.get(next) == distance.get(cur) + 1) {                   dfs(next, end, dict, nodeNeighbors, distance, solution, res);               }            }       }                  solution.remove(solution.size()-1);   }  public static void main(String[] args)  {    Solution test = new Solution();    String beginWord = "hit";    String endWord = "cog";    String[] wordList = {"hot","dot","dog","lot","log"};    Set<String> mySet = new HashSet<String>();    Collections.addAll(mySet, wordList);    test.findLadders(beginWord,endWord, mySet);  }}

[hot],hit

distance=={hit=0}

{lot=[], hit=[], log=[], dot=[], cog=[], hot=[], dog=[]}

[dot, lot],hot

distance=={hit=0, hot=1}

{lot=[], hit=[hot], log=[], dot=[], cog=[], hot=[], dog=[]}

[dog, hot, lot],dot

distance=={lot=2, hit=0, dot=2, hot=1}

{lot=[], hit=[hot], log=[], dot=[], cog=[], hot=[dot, lot], dog=[]}

[dot, log, hot],lot

distance=={lot=2, hit=0, dot=2, hot=1, dog=3}

{lot=[], hit=[hot], log=[], dot=[dog, hot, lot], cog=[], hot=[dot, lot], dog=[]}

[cog, log, dot],dog

distance=={lot=2, hit=0, log=3, dot=2, hot=1, dog=3}

{lot=[dot, log, hot], hit=[hot], log=[], dot=[dog, hot, lot], cog=[], hot=[dot, lot], dog=[]}

[cog, dog, lot],log

distance=={lot=2, hit=0, log=3, dot=2, cog=4, hot=1, dog=3}

{lot=[dot, log, hot], hit=[hot], log=[], dot=[dog, hot, lot], cog=[], hot=[dot, lot], dog=[cog, log, dot]}

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

看文倉www.kanwencang.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20170120/92626.html

文章列表

不含病毒。www.avast.com