127. Word Ladder

forsigner 发布于2019-08-14 14:25 / 578人阅读

摘要：题目解答主要解题思路的，把每一种可能的都放进去试，看能不能有一条线边到代码当然，这样的时间还不是最优化的，如果我们从两头扫，扫到中间任何一个能够串联起来都可以，如果没有找到可以串联的那么返回。

题目：
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.

解答：
主要解题思路的bfs，把每一种可能的character都放进去试，看能不能有一条线边到endWord.
代码：

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set wordList) {
        //BFS to solve the problem
        int count = 1;
        Set reached = new HashSet();
        reached.add(beginWord);
        wordList.add(endWord);
        
        while (!reached.contains(endWord)) {
            Set toAdd = new HashSet();
            for (String word : reached) {
                
                for (int i = 0; i < word.length(); i++) {
                    char[] chars = word.toCharArray();
                    for (char c = "a"; c <= "z"; c++) {
                        chars[i] = c;
                        String newWord = String.valueOf(chars);
                        if (wordList.contains(newWord)) {
                            toAdd.add(newWord);
                            wordList.remove(newWord);
                        }
                    }
                }
            }
            count++;
            if (toAdd.size() == 0) return 0;
            reached = toAdd;
        }
        return count;
    }
}

当然，这样的时间还不是最优化的，如果我们从两头扫，扫到中间任何一个word能够串联起来都可以，如果没有找到可以串联的word,那么返回0。代码如下：

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set wordList) {
        int count = 1;
        Set beginSet = new HashSet();
        Set endSet = new HashSet();
        Set visited = new HashSet();
        beginSet.add(beginWord);
        endSet.add(endWord);
        
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            
            
            if (beginSet.size() > endSet.size()) {
                Set temp = beginSet;
                beginSet = endSet;
                endSet = temp;
            }
            
            Set toAdd = new HashSet();
            for (String word : beginSet) {
                for (int i = 0; i < word.length(); i++) {
                    char[] chars = word.toCharArray();
                    for (char c = "a"; c <= "z"; c++) {
                        chars[i] = c;
                        String newWord = String.valueOf(chars);
                        if (endSet.contains(newWord)) return count + 1;
                        if (!visited.contains(newWord) && wordList.contains(newWord)) {
                            toAdd.add(newWord);
                            visited.add(newWord);
                        }
                    }
                }
            }
            count++;
            beginSet = toAdd;
        }
        return 0;
    }
}

私有云 idc机房托管 Ladder cdn服务器ip127 Word word 教程

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

转载请注明本文地址：https://www.ucloud.cn/yun/64997.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] Word Ladder 单词爬梯

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

pinecone 2019-08-14 12:24 评论0 收藏0
126. Word Ladder II

题目：Given two words (beginWord and endWord), and a dictionarys word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: Only one letter can be changed at a timeEach...

Tangpj 2019-08-14 14:28 评论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