leetcode127. Word Ladder

Galence 發(fā)布于2019-08-15 11:11 / 2016人閱讀

摘要：但是這種要遍歷所有的情況，哪怕是已經(jīng)超過(guò)最小操作次數(shù)的情況，導(dǎo)致代碼超時(shí)。其實(shí)從另一個(gè)角度來(lái)說(shuō)，這道題可以看做是廣度優(yōu)先算法的一個(gè)展示。按上文中的題目為例，可以將廣度優(yōu)先算法寫(xiě)成以下形式。

題目要求

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 transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
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.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

假設(shè)輸入兩個(gè)單詞beginWord，endWord以及一個(gè)字典。每一次操作只能對(duì)當(dāng)前單詞修改一個(gè)字符成為字典中的一個(gè)單詞。問(wèn)至少需要多少次操作可以將beginWord轉(zhuǎn)化為endWord。如果不可轉(zhuǎn)換則返回0。

思路與代碼

其實(shí)如果從遞歸的角度來(lái)看，并非不可以實(shí)現(xiàn)。每一種普遍情況也就是將當(dāng)前單詞修改一個(gè)字符成為當(dāng)前字典中的一個(gè)單詞。但是這種要遍歷所有的情況，哪怕是已經(jīng)超過(guò)最小操作次數(shù)的情況，導(dǎo)致代碼超時(shí)。其實(shí)從另一個(gè)角度來(lái)說(shuō)，這道題可以看做是廣度優(yōu)先算法的一個(gè)展示。

按上文中的題目為例，可以將廣度優(yōu)先算法寫(xiě)成以下形式。

    hit
    /
  hot
  / 
dot  lot
/    / 
dog  log
/     /
cog  cog

也就是說(shuō)，將每一層上可以生成的單詞全部列出來(lái)，然后再逐層遍歷，一旦出現(xiàn)一個(gè)單詞等于endWord，那么遍歷終止，將當(dāng)前遍歷的次數(shù)返回。這里要注意的是，需要將已經(jīng)遍歷的單詞記錄下來(lái)，從而不會(huì)發(fā)生重復(fù)的情況。

代碼

    //和字典中單詞比較是否可以轉(zhuǎn)換
    public boolean canTransform(String word1, String word2){
         for(int i = 0, count=0 ; i1) return false;
         }
         return true;
     }
     
     public int ladderLength(String beginWord, String endWord, List wordList){
         Queue q = new LinkedList();
         q.add(beginWord);
         int steps = 0;
         while(!q.isEmpty()){
             int size = q.size();
             for(int i = 0 ;i iterator = wordList.iterator() ; iterator.hasNext();){
                     String current = iterator.next();
                     if(canTransform(current, temp)){
                         iterator.remove();
                         q.offer(current);
                     }
                 }
             }
            steps++;

         }
         return 0;
     }

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~