127. Word-Ladder

difficulty: Medium

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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:

1. Only one letter can be changed at a time.

2. Each transformed word must exist in the word list.

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.

Example 1:

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Example 2:

Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Method One

这是我独立写的，只是单侧 bfs.

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>(wordList);
        if(  !dict.contains(endWord)  ) {
            return 0;
        }
        dict.add(beginWord);
        Map<String, Set<String>> map = new HashMap<>();
        for(String word : dict) {
            map.putIfAbsent(word, new HashSet<String>() );
            for(String next : wordList) {
                if( next == word || !isValidNeighbor(word, next) ) {
                    continue;
                }
                map.putIfAbsent(next, new HashSet<String>() );
                map.get(word).add(next);
                map.get(next).add(word);
            }
        }

        Set<String> used = new HashSet<>();
        Queue<String> bfs = new LinkedList<>();
        bfs.offer(beginWord);
        int steps = 0;
        while( !bfs.isEmpty()) {
            int size = bfs.size();
            steps += 1;
            while( size > 0 ) {
                size--;
                String cur = bfs.poll();
                used.add(cur);
                if( cur.compareTo(endWord) == 0 ) {
                    return steps;
                }
                for( String next : map.get(cur) ) {
                    if( used.contains(next) ) {
                        continue;
                    }
                    bfs.offer(next);
                }
            }
        }
        return 0;

    }

    public boolean isValidNeighbor (String s1, String s2 ) {
        if( s1.length() != s2.length() ) {
            return false;
        }
        int diffCount = 0;
        for(int i = 0; i < s1.length(); i++ ) {
            if( s1.charAt(i) != s2.charAt(i) ) {
                diffCount++;
                if(diffCount > 1) {
                    return false;
                }
            }
        }
        return diffCount == 1;
    }
}
​