[LeetCode/LintCode] Word Ladder

张金宝发布于2019-08-14 15:27 / 967人阅读

摘要：使用，利用其按层次操作的性质，可以得到最优解。这样可以保证这一层被完全遍历。每次循环取出的元素存为新的字符串。一旦找到和相同的字符串，就返回转换序列长度操作层数，即。

Problem

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

Notice

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

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

/*
考虑边界情况，如果`dict`为空，或`start.equals(end)`，则不满足`BFS`中循环的条件，在最后返回`0`.
如果是正常情况，`start`和`end`不等且`dict`包含转换需要的阶梯词组，那么转换次数加`2`，就是所求的转换序列长度。使用`BFS`，利用其按层次操作的性质，可以得到最优解。

**第一层while循环**：利用队列先进先出的原则，先用`size = q.size()`确定下一层`for`循环要从队列取出`size`个元素。这样可以保证这一层被完全遍历。当里面的三层`for`循环结束，即`q`的前`size`个元素全部遍历过之后，操作次数`count++`.
**第二层for循环**：对当前这一层的`size`个元素进行遍历。每次循环取出的元素存为新的字符串`cur`。
**第三层for循环**：遍历字符串`cur`的每个字符。
**第四层for循环**：将遍历到的`cur`的第`i`个字符换成从`a`到`z`的26个字母，存为新字符串`word`。然后查找`dict`里是否包含`word`：若存在，则从`dict`中删除此元素防止以后重复使用（无限循环），并将这个元素放入队列`q`，用于下一层的`BFS`循环。一旦找到和`end`相同的字符串，就返回`转换序列长度 = 操作层数 + 2`，即`count+2`。
*/

Solution Update 2018-9

class Solution {
    public int ladderLength(String beginWord, String endWord, List wordList) {
        Set dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) return 0;
        
        Set existed = new HashSet<>();
        existed.add(beginWord);
        int count = 1;
        
        while (!existed.contains(endWord)) { //当existed集合里包含了endWord，跳出while循环并返回步数count
            Set wanted = new HashSet<>();
            for (String s: existed) {
                for (int i = 0; i < s.length(); i++) {
                    for (char ch = "a"; ch <= "z"; ch++) {
                        StringBuilder sb = new StringBuilder(s);
                        sb.setCharAt(i, ch);
                        String str = sb.toString(); //找到了下一个词str
                        if (dict.contains(str)) {   //如果下一个词在dict里，从dict放入wanted
                            wanted.add(str);
                            dict.remove(str);
                        }
                    }
                }
            }
            //此时existed中所有词都找到了下一个词的集合，存在wanted中
            
            //如果wanted为空，则existed中的所有词都不存在下一个变化，return 0
            if (wanted.size() == 0) return 0;
            
            //否则交换existed和wanted，步数count+1，继续查找下一步变化
            count++;
            existed = wanted;
        }
        
        return count;
    }
}

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

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

[LeetCode/LintCode] Word Search

摘要：当递归到第次时，被调用了次。说明整个已经被找到，返回。回到函数，遍历整个数组，当函数返回时，才返回否则在循环结束之后返回。 Problem Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially a...

Aceyclee 2019-08-14 15:28 评论0 收藏0
[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 评论0 收藏0
[LeetCode/LintCode] Sentence Similarity

Problem Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar. For example, great acting skills a...

dreamtecher 2019-08-16 12:44 评论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
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