<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    IT技術小屋

    秋風秋雨,皆入我心

      BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
      38 隨筆 :: 1 文章 :: 19 評論 :: 0 Trackbacks
    Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, 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"]
    Return
      [
        ["hit","hot","dot","dog","cog"],
        ["hit","hot","lot","log","cog"]
      ]
    Note:
    All words have the same length.
    All words contain only lowercase alphabetic characters.

    這個題目應該算是leetcode上比較難的題目了。剛開始我采用了和Word Ladder相似的做法,只是用ArrayList記錄了當前變換路徑,在小數據的情況下可以Accept,但是大數據超時。究其原因,是由于為每個當前節點記錄變換路徑的時候,需要復制之前的ArrayList,這個時間開銷較大。
    其實,我們可以采用一個Map<String, HashSet<String>>結構,記錄字典單詞的每一個前驅,這樣我們可以從end反向遍歷,構造出轉換路徑。
    同時,我利用了兩個ArrayList,交替記錄上一層和下一層的節點,如果下一層節點為空,則不存在路徑,立即返回。如果下一層中出現了end,證明找到了所有的最短路徑,停止搜索開始構造路徑。實現代碼如下:
     1 public class WordLadderII {
     2     private void GeneratePath(Map<String, ArrayList<String>> prevMap,
     3             ArrayList<String> path, String word,
     4             ArrayList<ArrayList<String>> ret) {
     5         if (prevMap.get(word).size() == 0) {
     6             path.add(0, word);
     7             ArrayList<String> curPath = new ArrayList<String>(path);
     8             ret.add(curPath);
     9             path.remove(0);
    10             return;
    11         }
    12 
    13         path.add(0, word);
    14         for (String pt : prevMap.get(word)) {
    15             GeneratePath(prevMap, path, pt, ret);
    16         }
    17         path.remove(0);
    18     }
    19 
    20     public ArrayList<ArrayList<String>> findLadders(String start, String end,
    21             HashSet<String> dict) {
    22         ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();
    23         Map<String, ArrayList<String>> prevMap = new HashMap<String, ArrayList<String>>();
    24         dict.add(start);
    25         dict.add(end);
    26         for (String d : dict) {
    27             prevMap.put(d, new ArrayList<String>());
    28         }
    29         ArrayList<HashSet<String>> candidates = new ArrayList<HashSet<String>>();
    30         candidates.add(new HashSet<String>());
    31         candidates.add(new HashSet<String>());
    32         int current = 0;
    33         int previous = 1;
    34         candidates.get(current).add(start);
    35         while (true) {
    36             current = current == 0 ? 1 : 0;
    37             previous = previous == 0 ? 1 : 0;
    38             for (String d : candidates.get(previous)) {
    39                 dict.remove(d);
    40             }
    41             candidates.get(current).clear();
    42             for (String wd : candidates.get(previous)) {
    43                 for (int pos = 0; pos < wd.length(); ++pos) {
    44                     StringBuffer word = new StringBuffer(wd);
    45                     for (int i = 'a'; i <= 'z'; ++i) {
    46                         if (wd.charAt(pos) == i) {
    47                             continue;
    48                         }
    49 
    50                         word.setCharAt(pos, (char) i);
    51 
    52                         if (dict.contains(word.toString())) {
    53                             prevMap.get(word.toString()).add(wd);
    54                             candidates.get(current).add(word.toString());
    55                         }
    56                     }
    57                 }
    58             }
    59 
    60             if (candidates.get(current).size() == 0) {
    61                 return ret;
    62             }
    63             if (candidates.get(current).contains(end)) {
    64                 break;
    65             }
    66         }
    67 
    68         ArrayList<String> path = new ArrayList<String>();
    69         GeneratePath(prevMap, path, end, ret);
    70 
    71         return ret;
    72     }
    73 }
    posted on 2014-01-02 13:59 Meng Lee 閱讀(869) 評論(0)  編輯  收藏 所屬分類: Leetcode
    主站蜘蛛池模板: 久久青青草原亚洲av无码app | 日韩中文字幕免费| 国产精品亚洲片在线花蝴蝶| 综合亚洲伊人午夜网| 蜜臀AV免费一区二区三区| 亚洲精品无码高潮喷水A片软| 久久久久久久亚洲精品| 99无码人妻一区二区三区免费| 亚洲AV永久无码天堂影院| 亚洲午夜无码久久久久| 国产三级在线观看免费| 中国一级特黄高清免费的大片中国一级黄色片 | www在线观看播放免费视频日本| 亚洲综合激情视频| 亚洲国产成人爱av在线播放| 亚洲成年人免费网站| 日本一区二区三区免费高清在线 | 你懂的免费在线观看| 77777午夜亚洲| 狠狠色伊人亚洲综合成人| 蜜桃精品免费久久久久影院| 久久福利青草精品资源站免费| 亚洲av无码av在线播放| 久久精品国产亚洲精品2020| 亚洲av无码乱码在线观看野外 | 亚洲精品福利视频| 在线永久免费观看黄网站| 99精品视频免费观看| 国产福利电影一区二区三区,免费久久久久久久精 | 99久久精品国产亚洲| 亚洲精品视频在线观看你懂的| 成人免费AA片在线观看| 男人都懂www深夜免费网站| 免费国产污网站在线观看不要卡 | 中文字幕在线成人免费看| 亚洲av无码成人精品区一本二本| 91亚洲精品自在在线观看| 亚洲AV永久无码精品成人| 国产偷国产偷亚洲高清日韩 | 国产成人综合亚洲AV第一页| 精品免费国产一区二区三区 |