[LeetCode/LintCode] Word Ladder

張金寶發布于2019-08-14 15:27 / 968人閱讀

摘要：使用，利用其按層次操作的性質，可以得到最優解。這樣可以保證這一層被完全遍歷。每次循環取出的元素存為新的字符串。一旦找到和相同的字符串，就返回轉換序列長度操作層數，即。

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;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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