leetcode-127.单词接龙

127. 单词接龙

难度困难

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：

1
2
3

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

1
2
3

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同

超时代码：

// 超出时间限制
class Solution {
    boolean p = false;
    int min = Integer.MAX_VALUE;
    Map< String, Integer > map = new HashMap<>();
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        int[] flag = new int[ wordList.size() ];
        Map<String, Integer> t = new HashMap<>();
        for ( String s : wordList ) {
            t.put(s, 0);
        }  
        for ( int i = 0; i < wordList.size(); i ++ ) {
            if( nextWord( beginWord,  wordList.get( i ) ) ) {
                bfs( wordList.get( i ), endWord, wordList, i, 2, new HashMap<>(t) );
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
    
    public void bfs(String beginWord, String endWord, List<String> wordList, int index, int count, Map<String, Integer> t ) {
        if ( count >= min )
            return;
        t.put( beginWord, 1 );


        if ( beginWord.equals( endWord ) ) {
            // System.out.println("===================================    " + count);
            min = count < min ? count : min;
            return;
        }

        if ( map.containsKey( beginWord + " " + endWord ) ) {
            if ( count >= min )
                return;
        }

        for ( int i = 0; i < wordList.size(); i ++ ) {
            if ( t.get( wordList.get(i) ) == 0 && nextWord( beginWord,  wordList.get( i ) ) ) {
                bfs( wordList.get( i ), endWord, wordList, i, count + 1, new HashMap<>( t ) );
            }

        }
        map.put( beginWord + " " + endWord, 0 );
        return;

    }

    public boolean nextWord( String beginWord, String word ) {
        if ( beginWord.equals( word ) || beginWord.length() != word.length() ) {
            return false;
        }
        int n = 0;
        for( int i = 0; i < beginWord.length(); i ++ ) {
            
            if(  beginWord.charAt( i ) != word.charAt( i ) ) {
                n ++;
                if ( n > 1 ) {
                    return false;
                }
            }
        }
        return true;
    }

}

正解：广度优先搜索

思路：

分析题意：

「转换」意即：两个单词对应位置只有一个字符不同，例如 “hit” 与 “hot”，这种转换是可以逆向的，因此，根据题目给出的单词列表，可以构建出一个无向（无权）图；

如果一开始就构建图，每一个单词都需要和除它以外的另外的单词进行比较，复杂度是 O(NwordLen)，这里 NN 是单词列表的长度；
为此，我们在遍历一开始，把所有的单词列表放进一个哈希表中，然后在遍历的时候构建图，每一次得到在单词列表里可以转换的单词，复杂度是 O(26×wordLen)，借助哈希表，找到邻居与 N 无关；
使用 BFS 进行遍历，需要的辅助数据结构是：
队列；
visited 集合。说明：可以直接在 wordSet (由 wordList 放进集合中得到)里做删除。但更好的做法是新开一个哈希表，遍历过的字符串放进哈希表里。这种做法具有普遍意义。绝大多数在线测评系统和应用场景都不会在意空间开销。

class Solution {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 第 1 步：先将 wordList 放到哈希表里，便于更快地（相对于链表）判断某个单词是否在 wordList 里
        Set<String> wordSet = new HashSet<>(wordList);
        if (wordSet.size() == 0 || !wordSet.contains(endWord)) {
            return 0;
        }
        wordSet.remove(beginWord);
        
        // 第 2 步：图的广度优先遍历，必须使用队列和表示是否访问过的 visited 哈希表
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        
        // 第 3 步：开始广度优先遍历，包含起点，因此初始化的时候步数为 1
        int step = 1;
        while (!queue.isEmpty()) {
            int currentSize = queue.size();
            for (int i = 0; i < currentSize; i++) {
                // 依次遍历当前队列中的单词
                String currentWord = queue.poll();
                // 如果 currentWord 能够修改 1 个字符与 endWord 相同，则返回 step + 1
                if (changeWordEveryOneLetter(currentWord, endWord, queue, visited, wordSet)) {
                    return step + 1;
                }
            }
            step++;
        }
        return 0;
    }

    /**
     * 尝试对 currentWord 修改每一个字符，看看是不是能与 endWord 匹配
     */
    private boolean changeWordEveryOneLetter(String currentWord, String endWord,
                                             Queue<String> queue, Set<String> visited, Set<String> wordSet) {
        char[] charArray = currentWord.toCharArray();
        for (int i = 0; i < endWord.length(); i++) {
            // 先保存，然后恢复
            char originChar = charArray[i];
            for (char k = 'a'; k <= 'z'; k++) {
                if (k == originChar) {
                    continue;
                }
                // 修改一个字母
                charArray[i] = k;
                // char[] --> String
                String nextWord = String.valueOf(charArray);
                if (wordSet.contains(nextWord)) {
                    if (nextWord.equals(endWord)) {
                        return true;
                    }
                    if (!visited.contains(nextWord)) {
                        queue.add(nextWord);
                        // 注意：添加到队列以后，必须马上标记为已经访问
                        visited.add(nextWord);
                    }
                }
            }
            // 恢复
            charArray[i] = originChar;
        }
        return false;
    }
}

其然乐衣

127. 单词接龙