本文共 3687 字，大约阅读时间需要 12 分钟。

https://oj.leetcode.com/problems/word-ladder/

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence 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"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",

return its length 5.

 public int ladderLength(String start, String end, Set<String> dict)

这一题其实就是一个经典的图论题，怎么找最短路径。准确的说是找任意一条最短路径并返回长度即可。我们可以考虑DFS或者BFS。事实上DFS在这题如果不考虑很多的截枝条件根本没办法过ACCEPT。相反BFS就简单很多了。这就是BFS比DFS的优势所在了。DFS如果不做任何截枝处理和考虑，它总会跑完所有可能的路径不管深度是多少。但是在这里我们需要找一个尽量“不深”的路径，所以我们还是优先考虑BFS的好。当然，除了BFS之外，我们还要记录我们之前visit过的点以免重复路径。事实上，由于这题AC的条件比较苛刻，我们对于BFS，也可能需要考虑一种类似截枝的东西。我先来给大家对比两段代码好了：

public int ladderLength(String start, String end, Set
   
     dict) {        Queue
    
      string_queue = new LinkedList
     
      ();        HashSet
      
        visited = new HashSet
       
        ();        string_queue.add(start);        int cur_level = 1;        int cur_size = 1;        while(!string_queue.isEmpty()){            String cur_string = string_queue.poll();            visited.add(cur_string);            if(cur_string.equals(end)){                return cur_level;            }            char[] str_to_char = cur_string.toCharArray();            for(int i = 0; i < str_to_char.length; i++){                char tmp = str_to_char[i];                for(char ch = 'a'; ch <= 'z'; ch++){                    if(ch == tmp)                        continue;                    str_to_char[i] = ch;                    String candidate = new String(str_to_char);                    if(dict.contains(candidate) && !visited.contains(candidate)){                        string_queue.add(candidate);                    }                }                str_to_char[i] = tmp;            }            cur_size--;            if(cur_size == 0){                cur_level++;                cur_size = string_queue.size();            }        }        return 0;    }
       
      
     
    
   

public int ladderLength(String start, String end, Set
   
     dict) {        Queue
    
      string_queue = new LinkedList
     
      ();        HashSet
      
        visited = new HashSet
       
        ();        string_queue.add(start);        int cur_level = 1;        int cur_size = 1;        while(!string_queue.isEmpty()){            String cur_string = string_queue.poll();            if(cur_string.equals(end)){                return cur_level;            }            char[] str_to_char = cur_string.toCharArray();            for(int i = 0; i < str_to_char.length; i++){                char tmp = str_to_char[i];                for(char ch = 'a'; ch <= 'z'; ch++){                    if(ch == tmp)                        continue;                    str_to_char[i] = ch;                    String candidate = new String(str_to_char);                    if(dict.contains(candidate) && !visited.contains(candidate)){                        string_queue.add(candidate);                        visited.add(candidate);                    }                }                str_to_char[i] = tmp;            }            cur_size--;            if(cur_size == 0){                cur_level++;                cur_size = string_queue.size();            }        }        return 0;    }
       
      
     
    
   

两段几乎一模一样的代码，上面的TLE了，下面的AC了。到底是为什么？原因就在与我更新visited的地方变了。上面那个是走到哪才更新visited，下面那个是我在往下加下一层节点的时候，我就更新visited了。前一种情况相当于我在BFS的情况下跑满了所有可能的路径（到出现答案的那一层）。而后一种情况相当于我截枝了。也就是在同一层出现过的节点，我只要其中最先出现的那个路径，其余路径哪怕完全不同，我也不予考虑。一般情况下DAG的题目visited这样的标记只是为了防止出现循环路径。但这里我们为了追求最大效率还要用来做截枝。

转载地址：http://xgaxb.baihongyu.com/