国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

127. Word Ladder

forsigner / 870人閱讀

摘要:題目解答主要解題思路的,把每一種可能的都放進去試,看能不能有一條線邊到代碼當然,這樣的時間還不是最優(yōu)化的,如果我們從兩頭掃,掃到中間任何一個能夠串聯(lián)起來都可以,如果沒有找到可以串聯(lián)的那么返回。

題目:
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;
    }
}

當然,這樣的時間還不是最優(yōu)化的,如果我們從兩頭掃,掃到中間任何一個word能夠串聯(lián)起來都可以,如果沒有找到可以串聯(lián)的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;
    }
}

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

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/64997.html

相關(guān)文章

  • 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 評論0 收藏0
  • 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 評論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 評論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 評論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

發(fā)表評論

0條評論

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