126. Word Ladder II

Tangpj 發(fā)布于2019-08-14 14:28 / 1973人閱讀

題目：
Given two words (beginWord and endWord), and a dictionary"s word list, find all shortest transformation sequence(s) 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"]
Return
[

["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]

]

解答：

public class Solution {
    List> result;
    List list;
    Map> map;
    public List> findLadders(String beginWord, String endWord, Set wordList) {
        result = new ArrayList>();
        if (wordList.size() == 0) return result;
        
        list = new LinkedList();
        map = new HashMap>();
        int curt = 1, next = 0;
        boolean found = false;
        Set unvisited = new HashSet(wordList);
        Set visited = new HashSet();
        Queue queue = new ArrayDeque();
        
        queue.add(beginWord);
        unvisited.add(endWord);
        unvisited.remove(beginWord);
        //BFS
        while (!queue.isEmpty()) {
            String word = queue.poll();
            curt--;
            for (int i = 0; i < word.length(); i++) {
                StringBuilder sb = new StringBuilder(word);
                for (char ch = "a"; ch <= "z"; ch++) {
                    sb.setCharAt(i, ch);
                    String newWord = sb.toString();
                    if (unvisited.contains(newWord)) {
                        if (visited.add(newWord)) {
                            next++;
                            queue.add(newWord);
                        }
                        
                        if (!map.containsKey(newWord)) {
                            map.put(newWord, new LinkedList());
                        }
                        map.get(newWord).add(word);
                        
                        if (newWord.equals(endWord) && !found) found = true;
                    }
                }
            }
            if (curt == 0) {
                if (found) break;
                curt = next;
                next = 0;
                unvisited.removeAll(visited);
                visited.clear();
            }
        }
        
        backTrace(endWord, beginWord);
        return result;
    }
    
    public void backTrace(String word, String beginWord) {
        if (word.equals(beginWord)) {
            list.add(0, beginWord);
            result.add(new ArrayList(list));
            list.remove(0);
            return;
        }
        list.add(0, word);
        if (map.get(word) != null) {
            for (String s : map.get(word)) {
                backTrace(s, beginWord);
            }
        }
        list.remove(0);
    }
}

GPU云服務器云服務器 Ladder 網(wǎng)易126 python 126 網(wǎng)易126am

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65031.html

leetcode126. Word Ladder II

摘要：題目要求相比于，要求返回所有的最短路徑。至于如何生成該有向圖，則需要通過廣度優(yōu)先算法，利用隊列來實現(xiàn)。將每一層的分別入棧。如果遇到則至該層結(jié)尾廣度優(yōu)先算法結(jié)束。通過這種方式來防止形成圈。題目要求 Given two words (beginWord and endWord), and a dictionarys word list, find all shortest transfo...

cooxer 2019-08-15 11:13 評論0 收藏0
[LeetCode] 126. Word Ladder II

摘要：存放過程中的所有集合為所有的結(jié)尾，則順序存放這個結(jié)尾對應的中的所有存放同一個循環(huán)的新加入的，在下一個循環(huán)再依次對其中元素進行進一步的把首個字符串放入新，再將放入，并將鍵值對放入，進行初始化 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

摘要：題目解答主要解題思路的，把每一種可能的都放進去試，看能不能有一條線邊到代碼當然，這樣的時間還不是最優(yōu)化的，如果我們從兩頭掃，掃到中間任何一個能夠串聯(lián)起來都可以，如果沒有找到可以串聯(lián)的那么返回。題目：Given two words (beginWord and endWord), and a dictionarys word list, find the length of short...

forsigner 2019-08-14 14:25 評論0 收藏0
[Leetcode] Word Ladder 單詞爬梯

摘要：另外，為了避免產(chǎn)生環(huán)路和重復計算，我們找到一個存在于字典的新的詞時，就要把它從字典中移去。代碼用來記錄跳數(shù)控制來確保一次循環(huán)只計算同一層的節(jié)點，有點像二叉樹遍歷循環(huán)這個詞從第一位字母到最后一位字母循環(huán)這一位被替換成個其他字母的情況 Word Ladder Given two words (beginWord and endWord), and a dictionary, find t...

pinecone 2019-08-14 12:24 評論0 收藏0
leetcode127. Word Ladder

摘要：但是這種要遍歷所有的情況，哪怕是已經(jīng)超過最小操作次數(shù)的情況，導致代碼超時。其實從另一個角度來說，這道題可以看做是廣度優(yōu)先算法的一個展示。按上文中的題目為例，可以將廣度優(yōu)先算法寫成以下形式。題目要求 Given two words (beginWord and endWord), and a dictionarys word list, find the length of short...

Galence 2019-08-15 11:11 評論0 收藏0