[LeetCode] Word Ladder

发布时间:2019-08-06 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了[LeetCode] Word Ladder脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

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 intermediate word must exist in the word list
For example,

Given:
beginWord = "hIT"
endWord = "cog"
wordList = ["hot","dot","dog","lot","LOG"]
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.


Solution1 single-ended BFS
Typical shortest path PRoblem, use BFS. When using BFS, need to mark visited string. In the problem, we can simply remove it from the dictionary set. Edge case check: remove beginWord from dictionary list if applicable. Tree grows from one side and become unevenly.

[LeetCode] Word Ladder

Solution2 double-ended BFS
beginSet, endSet Stores all the string reachable from beginWord, endWord resPEctively. The rest process is the same as single-ended BFS. Difference: in each iteration(of one level), use the set that has the fewer string. In this approach, tree grows evenly.

[LeetCode] Word Ladder

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if (beginWord.equals(endWord)) {
            return 1;
        }
        int len = 2;
        Queue<String> begin = new LinkedList<>();
        Queue<String> end = new LinkedList<>();
        begin.offer(beginWord);
        end.offer(endWord);
        if (wordList.contains(beginWord)) {
            wordList.remove(beginWord);
        }
        if (wordList.contains(endWord)) {
            wordList.remove(endWord);
        }
        
        
        while (@H_512_90@!begin.isEmpty() && !end.isEmpty()) {
            if (begin.size() > end.size()) {
                Queue<String> temp = begin;
                begin = end;
                end = temp;
            }
            int size = begin.size();
            for (int i = 0; i < size; i++) {
                String word = begin.poll();
                char[] temp = word.toCharArray();
                for (int j = 0; j < temp.length; j++) {
                    char oldChar = temp[j];
                    for (char c = @H_151_126@'a'; c <= 'z'; c++) {
                        temp[j] = c;
                        String transformed = new String(temp);
                        if (end.contains(transformed)) {
                            return len;
                        } else if (wordList.contains(transformed)) {
                            wordList.remove(transformed);
                            begin.offer(transformed);
                        }
                    }
                    temp[j] = oldChar;
                }
            }
            len++;
        }
        return 0;
    }
}

脚本宝典总结

以上是脚本宝典为你收集整理的[LeetCode] Word Ladder全部内容,希望文章能够帮你解决[LeetCode] Word Ladder所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。