LeetCode(127):単語ドラゴンボールWord Ladder(Java)

2019.8.9#プログラマー筆記試験必須#LeetCodeゼロブラシ個人メモ整理(継続更新)
この問題は実質的に図問題であり、各文字列と辞書内のドラゴン文字列(1文字の異なる文字列しかない)を無方向エッジ構築図とし、簡単なBFSに頼るだけで本題を解決することができる.
しかし、本題は図面を構築するのが難しく、各エッジの関係をどのように効率的に計算して格納するかが難しく、単純に3層サイクルで行うとタイムアウトします.ここでは,各文字列のすべてのテンプレート(順次各ビットの代わりに*を用いる)をkeyとし,テンプレートに適合するすべての文字列をvalue構築図とし,ループの複雑さを省くことができる.
トランスポートゲート:単語のドラゴンボール
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. 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.
2つの単語(beginWordとendWord)と辞書を指定し、beginWordからendWordへの最短変換シーケンスの長さを見つけます.変換には、次のルールが必要です.
変換するたびに1文字しか変更できません.変換中の中間単語は辞書の中の単語でなければなりません.説明:
このような変換シーケンスが存在しない場合は、0を返します.すべての単語は同じ長さを持っています.すべての単語は小文字だけで構成されています.辞書に重複する単語は存在しません.beginWordとendWordは空ではなく、両者が異なると仮定できます.

  1:

  :
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

  : 5
  :           "hit" -> "hot" -> "dot" -> "dog" -> "cog",       5。

   2:

  :
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

  :0
  :endWord "cog"      ，        。

import java.util.*;

/**
 *
 * 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.
 *       （beginWord   endWord）     ，    beginWord   endWord           。         ：
 *             。
 *                    。
 *
 */

public class WordLadder {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int len = beginWord.length();

        //       “a*b”  key，            value     ，         
        HashMap<String, ArrayList<String>> map = new HashMap<>();
        for(String str : wordList){
            for(int i = 0; i < len; i++){
                String pattern = str.substring(0, i) + "*" + str.substring(i + 1, len);
                map.putIfAbsent(pattern, new ArrayList<>());
                map.get(pattern).add(str);
            }
        }

        //      BFS，  HashSet          
        HashSet<String> set = new HashSet<>();
        LinkedList<String> list = new LinkedList<>();
        list.add(beginWord);
        int result = 1;
        while(!list.isEmpty()){
            int size = list.size();
            for(int i = 0; i < size; i++){
                String str = list.pollFirst();
                if(str.equals(endWord)){
                    return result;
                }
                for(int j = 0; j < len; j++){
                    String pattern = str.substring(0, j) + "*" + str.substring(j + 1, len);
                    ArrayList<String> nextList = map.getOrDefault(pattern, new ArrayList<>());
                    for(String next : nextList){
                        if(!set.contains(next)){
                            list.add(next);
                            set.add(next);
                        }
                    }
                }
            }
            result++;
        }
        return 0;
    }
}

#Coding 1時間、Copying 1秒.いいねを残してくれてありがとう