[Leetcode] Word Ladder 单词爬梯

pinecone 发布于2019-08-14 12:24 / 2542人阅读

摘要：另外，为了避免产生环路和重复计算，我们找到一个存在于字典的新的词时，就要把它从字典中移去。代码用来记录跳数控制来确保一次循环只计算同一层的节点，有点像二叉树遍历循环这个词从第一位字母到最后一位字母循环这一位被替换成个其他字母的情况

Word Ladder

Given two words (beginWord and endWord), and a dictionary, 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 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.
Note: Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.

广度优先搜索 复杂度

时间 O(N) 空间 O(N)

思路

因为要求最短路径，如果我们用深度优先搜索的话必须遍历所有的路径才能确定哪个是最短的，而用广度优先搜索的话，一旦搜到目标就可以提前终止了，而且根据广度优先的性质，我们肯定是先通过较短的路径搜到目标。另外，为了避免产生环路和重复计算，我们找到一个存在于字典的新的词时，就要把它从字典中移去。这么做是因为根据广度优先，我们第一次发现词A的路径一定是从初始词到词A最短的路径，对于其他可能再经过词A的路径，我们都没有必要再计算了。

代码

public class Solution {

    public int ladderLength(String beginWord, String endWord, Set wordDict) {
        Queue queue = new LinkedList();
        // step用来记录跳数
        int step = 2;
        queue.offer(beginWord);
        while(!queue.isEmpty()){
            int size = queue.size();
            // 控制size来确保一次while循环只计算同一层的节点，有点像二叉树level order遍历
            for(int j = 0; j < size; j++){
               String currWord = queue.poll();
                // 循环这个词从第一位字母到最后一位字母
                for(int i = 0; i < endWord.length(); i++){
                    // 循环这一位被替换成25个其他字母的情况
                    for(char letter = "a"; letter <= "z"; letter++){
                        StringBuilder newWord = new StringBuilder(currWord);
                        newWord.setCharAt(i, letter);
                        if(endWord.equals(newWord.toString())){
                            return step;    
                        } else if(wordDict.contains(newWord.toString())){
                            wordDict.remove(newWord.toString());
                            queue.offer(newWord.toString());
                        }
                    }
                } 
            }
            step++;
        }
        return 0;
    }
}

云服务器 GPU云服务器 Ladder 爬梯 LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64458.html

leetcode127. Word Ladder

摘要：但是这种要遍历所有的情况，哪怕是已经超过最小操作次数的情况，导致代码超时。其实从另一个角度来说，这道题可以看做是广度优先算法的一个展示。按上文中的题目为例，可以将广度优先算法写成以下形式。题目要求 Given two words (beginWord and endWord), and a dictionarys word list, find the length of short...

Galence 2019-08-15 11:11 评论0 收藏0
leetcode126. Word Ladder II

摘要：题目要求相比于，要求返回所有的最短路径。至于如何生成该有向图，则需要通过广度优先算法，利用队列来实现。将每一层的分别入栈。如果遇到则至该层结尾广度优先算法结束。通过这种方式来防止形成圈。题目要求 Given two words (beginWord and endWord), and a dictionarys word list, find all shortest transfo...

cooxer 2019-08-15 11:13 评论0 收藏0
[LeetCode/LintCode] Word Ladder

摘要：使用，利用其按层次操作的性质，可以得到最优解。这样可以保证这一层被完全遍历。每次循环取出的元素存为新的字符串。一旦找到和相同的字符串，就返回转换序列长度操作层数，即。 Problem Given two words (start and end), and a dictionary, find the length of shortest transformation sequence...

张金宝 2019-08-14 15:27 评论0 收藏0
[LeetCode] 126. Word Ladder II

摘要：存放过程中的所有集合为所有的结尾，则顺序存放这个结尾对应的中的所有存放同一个循环的新加入的，在下一个循环再依次对其中元素进行进一步的把首个字符串放入新，再将放入，并将键值对放入，进行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...

wayneli 2019-08-14 14:27 评论0 收藏0
127. Word Ladder

摘要：题目解答主要解题思路的，把每一种可能的都放进去试，看能不能有一条线边到代码当然，这样的时间还不是最优化的，如果我们从两头扫，扫到中间任何一个能够串联起来都可以，如果没有找到可以串联的那么返回。题目：Given two words (beginWord and endWord), and a dictionarys word list, find the length of short...

forsigner 2019-08-14 14:25 评论0 收藏0