成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Word Ladder 單詞爬梯

pinecone / 2572人閱讀

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

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.
廣度優(yōu)先搜索 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

因?yàn)橐笞疃搪窂?，如果我們用深度?yōu)先搜索的話必須遍歷所有的路徑才能確定哪個(gè)是最短的，而用廣度優(yōu)先搜索的話，一旦搜到目標(biāo)就可以提前終止了，而且根據(jù)廣度優(yōu)先的性質(zhì)，我們肯定是先通過較短的路徑搜到目標(biāo)。另外，為了避免產(chǎn)生環(huán)路和重復(fù)計(jì)算，我們找到一個(gè)存在于字典的新的詞時(shí)，就要把它從字典中移去。這么做是因?yàn)楦鶕?jù)廣度優(yōu)先，我們第一次發(fā)現(xiàn)詞A的路徑一定是從初始詞到詞A最短的路徑，對于其他可能再經(jīng)過詞A的路徑，我們都沒有必要再計(jì)算了。

代碼 
public class Solution {

    public int ladderLength(String beginWord, String endWord, Set wordDict) {
        Queue queue = new LinkedList();
        // step用來記錄跳數(shù)
        int step = 2;
        queue.offer(beginWord);
        while(!queue.isEmpty()){
            int size = queue.size();
            // 控制size來確保一次while循環(huán)只計(jì)算同一層的節(jié)點(diǎn)，有點(diǎn)像二叉樹level order遍歷
            for(int j = 0; j < size; j++){
               String currWord = queue.poll();
                // 循環(huán)這個(gè)詞從第一位字母到最后一位字母
                for(int i = 0; i < endWord.length(); i++){
                    // 循環(huán)這一位被替換成25個(gè)其他字母的情況
                    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;
    }
}

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

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

相關(guān)文章

  • leetcode127. Word Ladder

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

    Galence 評論0 收藏0

  • leetcode126. Word Ladder II

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

    cooxer 評論0 收藏0

  • [LeetCode/LintCode] Word Ladder

    摘要：使用，利用其按層次操作的性質(zhì)，可以得到最優(yōu)解。這樣可以保證這一層被完全遍歷。每次循環(huán)取出的元素存為新的字符串。一旦找到和相同的字符串，就返回轉(zhuǎn)換序列長度操作層數(shù)，即。 Problem Given two words (start and end), and a dictionary, find the length of shortest transformation sequence...

    張金寶 評論0 收藏0

  • [LeetCode] 126. Word Ladder II

    摘要：存放過程中的所有集合為所有的結(jié)尾，則順序存放這個(gè)結(jié)尾對應(yīng)的中的所有存放同一個(gè)循環(huán)的新加入的，在下一個(gè)循環(huán)再依次對其中元素進(jìn)行進(jìn)一步的把首個(gè)字符串放入新，再將放入，并將鍵值對放入，進(jìn)行初始化 Problem Given two words (start and end), and a dictionary, find all shortest transformation sequenc...

    wayneli 評論0 收藏0

  • 127. Word Ladder

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

    forsigner 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<