Problem:

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

• Only one letter can be changed at a time.
• Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Example:

Given: beginWord = “hit” endWord = “cog” wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

```public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Map<String, List<String>> map = new HashMap<>();
map.put(beginWord, new ArrayList<>());
for (String word : wordList){
map.put(word, new ArrayList<>());
}
for (String key : map.keySet()){
List<String> container = map.get(key);
for (String word : wordList){
if (oneDiff(key, word)){
}
}
map.put(key, container);
}
int ans = helper(map, beginWord, endWord, new HashSet<>());
return ans >= 1 << 30 ? 0 : ans;
}

private int helper(Map<String, List<String>> map,String beginWord, String endWord, Set<String> visited){
if (visited.contains(beginWord)) return 1<<30;
for (String find : map.get(beginWord)){
if (find.equals(endWord)){
visited.remove(beginWord);
return 2;
}
}
int min = Integer.MAX_VALUE;
for (String find : map.get(beginWord)){
int x = 1 + helper(map, find, endWord, visited);
min = Math.min(min, x);
}
visited.remove(beginWord);
return min;
}

private boolean oneDiff(String a, String b){
if (a.equals(b)) return false;
char[] aa = a.toCharArray();
char[] bb = b.toCharArray();

int oneDiff = 0;
for (int i = 0; i < aa.length; i++){
if (aa[i] != bb[i]){
oneDiff ++;
if (oneDiff >= 2) return false;
}
}
return true;
}```

```beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
wordList中编辑距离为1的单词有：
a. hot

a. dot
b. lot

a. cog

```public int ladderLength(String beginWord, String endWord, List<String> wordList) {
List<String> reached = new ArrayList<>();
Set<String> wordSet = new HashSet<>(wordList);
if(!wordSet.contains(endWord)) return 0;

int distance = 1;
while (!reached.contains(endWord)){ //到达该目的地
for (String each : reached){
for (int i = 0; i < each.length(); i++){
char[] chars = each.toCharArray();
for (char c = 'a';  c <= 'z'; c++){
chars[i] = c;
String wd = new String(chars);
if (wordSet.contains(wd)){
wordSet.remove(wd); //记录访问状态
}
}
}
}
distance ++;
if (toAdd.size() == 0) return 0; //没有编辑距离为1的单词
}
return distance;
}```

Problem:

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 transformed word must exist in the word list. Note that beginWord is not a transformed word.

Example:

Given: beginWord = “hit” endWord = “cog” wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] Return [ [“hit”,”hot”,”dot”,”dog”,”cog”], [“hit”,”hot”,”lot”,”log”,”cog”] ]

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

```public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Map<String, List<String>> map = new HashMap<>();
map.put(beginWord, new ArrayList<>());
for (String word : wordList){
map.put(word, new ArrayList<>());
}
for (String key : map.keySet()){
List<String> container = map.get(key);
for (String word : wordList){
if (oneDiff(key, word)){
}
}
map.put(key, container);
}
int distance = bfs(beginWord, endWord, wordList);
List<List<String>> ans = new ArrayList<>();
dfs(map, beginWord, endWord, ans, new ArrayList<>(), distance);
return ans;
}

private void dfs(Map<String, List<String>> map,String beginWord, String endWord, List<List<String>> ans, List<String> path, int distance){
if (distance == 0){
path.remove(path.size()-1);
return;
}
if (beginWord.equals(endWord)){
path.remove(path.size()-1);
return;
}
for (String find : map.get(beginWord)){
dfs(map, find, endWord, ans, path, distance-1);
}
path.remove(path.size()-1);
}

private int bfs(String beginWord, String endWord, List<String> wordList) {
List<String> reached = new ArrayList<>();
Set<String> wordSet = new HashSet<>(wordList);
if(!wordSet.contains(endWord)) return 0;

int distance = 1;
while (!reached.contains(endWord)){ //达到该目的地
for (String each : reached){
for (int i = 0; i < each.length(); i++){
char[] chars = each.toCharArray();
for (char c = 'a';  c <= 'z'; c++){
chars[i] = c;
String wd = new String(chars);
if (wordSet.contains(wd)){
wordSet.remove(wd);
}
}
}
}
distance ++;
if (toAdd.size() == 0) return 0;
}
return distance;
}

private boolean oneDiff(String a, String b){
if (a.equals(b)) return false;
char[] aa = a.toCharArray();
char[] bb = b.toCharArray();

int oneDiff = 0;
for (int i = 0; i < aa.length; i++){
if (aa[i] != bb[i]){
oneDiff ++;
if (oneDiff >= 2) return false;
}
}
return true;
}```

```一条可能的搜索路径：
hot ---> dot ---> dog ---> cog

hot ---> dot ---> tot ---> hot

```private int bfs(String beginWord, String endWord, Set<String> wordDict, Map<String, Integer> distanceMap,
Map<String, List<String>> map) {
if (!wordDict.contains(endWord))
return 0;
map.put(beginWord, new ArrayList<>());
for (String word : wordDict) {
map.put(word, new ArrayList<>());
}

queue.offer(beginWord);
distanceMap.put(beginWord, 1);

while (!queue.isEmpty()) {
int count = queue.size();
boolean foundEnd = false;
// 这种循环遍历很有意思，看作一个整体
for (int i = 0; i < count; i++) {
String cur = queue.poll();
int curDistance = distanceMap.get(cur);
List<String> neighbors = getNeighbors(cur, wordDict);
if (neighbors.size() == 0)
return 0;
for (String neighbor : neighbors) {
//存在环的情况，不去更新最短路径
if (!distanceMap.containsKey(neighbor)) {
distanceMap.put(neighbor, curDistance + 1);
if (endWord.equals(neighbor)) {
foundEnd = true;
} else {
queue.offer(neighbor);
}
}
}
}
//一旦抵到了endWord，我们就放弃建立后续的图
if (foundEnd)
break;
}
return distanceMap.get(endWord);
}```

```    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
Map<String, List<String>> map = new HashMap<>();
Map<String, Integer> distanceMap = new HashMap<>();
Set<String> wordDict = new HashSet<>(wordList);
int distance = bfs(beginWord, endWord, wordDict, distanceMap, map);
List<List<String>> ans = new ArrayList<>();
if (distance == 0)
return ans;
dfs(map, beginWord, endWord, ans, new ArrayList<>(), distance, distanceMap);
return ans;
}

private void dfs(Map<String, List<String>> map, String beginWord, String endWord, List<List<String>> ans,
List<String> path, int distance, Map<String, Integer> distanceMap) {
if (distance == 0) {
path.remove(path.size() - 1);
return;
}
if (beginWord.equals(endWord)) {
path.remove(path.size() - 1);
return;
}
for (String find : map.get(beginWord)) {
if (!distanceMap.containsKey(find))
continue;
if (distanceMap.get(beginWord) + 1 == distanceMap.get(find))
dfs(map, find, endWord, ans, path, distance - 1, distanceMap);
}
path.remove(path.size() - 1);
}

private int bfs(String beginWord, String endWord, Set<String> wordDict, Map<String, Integer> distanceMap,
Map<String, List<String>> map) {
if (!wordDict.contains(endWord))
return 0;
map.put(beginWord, new ArrayList<>());
for (String word : wordDict) {
map.put(word, new ArrayList<>());
}

queue.offer(beginWord);
distanceMap.put(beginWord, 1);

while (!queue.isEmpty()) {
int count = queue.size();
boolean foundEnd = false;
for (int i = 0; i < count; i++) {
String cur = queue.poll();
int curDistance = distanceMap.get(cur);
List<String> neighbors = getNeighbors(cur, wordDict);
if (neighbors.size() == 0)
return 0;
for (String neighbor : neighbors) {
if (!distanceMap.containsKey(neighbor)) {
distanceMap.put(neighbor, curDistance + 1);
if (endWord.equals(neighbor)) {
foundEnd = true;
} else {
queue.offer(neighbor);
}
}
}
}
if (foundEnd)
break;
}
return distanceMap.get(endWord);
}

private List<String> getNeighbors(String word, Set<String> wordList) {
List<String> ans = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
char[] cc = word.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
cc[i] = c;
String newWord = new String(cc);
if (wordList.contains(newWord)) {
if (newWord.equals(word))
continue;
}
}
}
return ans;
}```

DFS是一个典型的回溯+剪枝的递归方法，凡是函数返回的地方，我们都需要进行状态还原，注意再注意。

0 条评论

• 算法细节系列（23）：回溯

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• Special Binary String

Example 1: Input: S = “11011000” Output: “11100100” Explanation: The str...

• 微信公众号H5支付遇到的那些坑

简史 官方文档说的很清楚，商户已有H5商城网站，用户通过消息或扫描二维码在微信内打开网页时，可以调用微信支付完成下单购买的流程。 当然，最近微信支付平台也加入了...

• 微信公众号H5支付遇到的那些坑

官方文档说的很清楚，商户已有H5商城网站，用户通过消息或扫描二维码在微信内打开网页时，可以调用微信支付完成下单购买的流程。

• 老板看了我的代码，直呼“666”，说涨工资！

如何更规范化编写Java 代码的重要性想必毋需多言，其中最重要的几点当属提高代码性能、使代码远离Bug、令代码更优雅。

• 当我遵循了这 16 条规范写代码，同事只对我说了三个字： 666

Many of the happiest people are those who own the least. But are we really so ha...

• 如何更规范化编写 Java 代码

如何更规范化编写 Java 代码的重要性想必毋需多言，其中最重要的几点当属提高代码性能、使代码远离 Bug、令代码更优雅。

• Java-String.intern的深入研究

When---什么时候需要了解String的intern方法： 面试的时候（蜜汁尴尬）！虽然不想承认，不过面试的时候经常碰到这种高逼格的问题来考察我们是否真正理...