<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| 久久免费精品视频| 亚洲中文字幕在线第六区| 特级毛片爽www免费版| 亚洲 另类 无码 在线| 国产天堂亚洲国产碰碰| 国产美女精品视频免费观看| 亚洲人成自拍网站在线观看| 成年美女黄网站18禁免费| 国产日本亚洲一区二区三区| 一二三四在线播放免费观看中文版视频 | 91免费国产在线观看| 亚洲女人初试黑人巨高清| 91久久成人免费| 亚洲六月丁香婷婷综合| 成人免费无码视频在线网站| 亚洲一日韩欧美中文字幕在线| 在线观看免费a∨网站| 黑人粗长大战亚洲女2021国产精品成人免费视频 | 亚洲人成在线播放网站岛国| 在线看无码的免费网站| 亚洲区精品久久一区二区三区| 国产成人A在线观看视频免费| 亚洲国产高清国产拍精品| 日韩亚洲精品福利| 你是我的城池营垒免费观看完整版| 国产AV无码专区亚洲精品| h视频在线免费看| 亚洲变态另类一区二区三区 | 理论片在线观看免费| 亚洲精品乱码久久久久久蜜桃不卡| 四虎成人精品永久免费AV| 国产色在线|亚洲| 亚洲A∨午夜成人片精品网站| 色播在线永久免费视频网站| 亚洲成aⅴ人片在线观| 免费国产精品视频| 99精品视频免费在线观看| 亚洲AV女人18毛片水真多| 久久久久久a亚洲欧洲aⅴ|