Question

Formatted question description: https://leetcode.ca/all/127.html

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.

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.


@tag-backtracking

Algorithm

In order to boost the search efficiency of the dictionary, we use HashSet to save all the words.

Then we need a HashMap to establish a mapping between the ending word of a certain path and the length of the path, and map the starting word to 1.

Since it is BFS, we need a queue, put the starting word into the queue, start the loop of the queue, take out the first word of the queue, and then replace the characters in each position with 26 letters. If itself and the ending words are the same, the value of the extracted word in the hash table can be encremented by one.

If the replacement word exists in the dictionary but does not exist in the hash table, the replacement word is queued, and the value in the hash table is mapped to the previous word plus one. Return 0 if the loop is complete.

Code

Java


public class Word_Ladder {

    public class Solution {
        public int ladderLength(String start, String end, Set<String> dict) {

            // bfs to make sure its shortest

            if (start.equals(end)) {
                return 0;
            }

            dict.add(end); // !!!@note: 别忘了

            Queue<String> q = new LinkedList<String>();
            HashSet<String> visited = new HashSet<String>();
            int level = 1;
            int currentLevelCount = 1;
            int newLevelCount = 0;

            q.offer(start);
            visited.add(start);

            while (!q.isEmpty()) {

                String s = q.poll();
                currentLevelCount--; // @note: 这样少了queue的操作

                for (int i = 0; i < s.length(); i++) {
                    char[] array = s.toCharArray(); // @note:@memorize: char array的效率要高

                    for (char c = 'a'; c <= 'z'; c++) {
                        array[i] = c;
                        String each = new String(array);

                        if (each.equals(end)) {
                            return level + 1;
                        }

                        // @note: 这里没有检查是不是string生成了他自己,因为自己已经在visited里面了。但是还是不太明显,不推荐。
                        //          加一个if没什么,逻辑更清晰
                        if (dict.contains(each) && !visited.contains(each)) {
                            q.offer(each);
                            visited.add(each);
                            newLevelCount++;
                        }
                    }
                }

                // @note: must be after trying the last word of currentLevel, then update
                if (currentLevelCount == 0) {
                    currentLevelCount = newLevelCount;
                    newLevelCount = 0;
                    level++;

                }

            }

            return 0; // 如果没找到,那么就是0
        }

    }

    // 不用string接起来,直接char[]
    public class Solution_bfs_over_time {
        public int ladderLength(String start, String end, Set<String> dict) {

            // bfs to make sure its shortest

            if (start.equals(end))  return 0;

            dict.add(end); // !!!@note: 别忘了

            Queue<String> q = new LinkedList<String>();
            HashSet<String> visited = new HashSet<String>();
            int count = 1;

            q.offer(start);
            q.offer(null); // null is used marking level end

            while (!q.isEmpty()) {

                if (q.peek() == null) {
                    count++;
                    q.poll(); // pop null at head

                    // @note@note: or else, null poll, nulll offer. infinite looping
                    if (q.isEmpty())
                        break;
                    else {
                        q.offer(null); // enqueue new null
                        continue;
                    }
                }

                String s = q.poll();
                visited.add(s);

                char[] array = s.toCharArray();
                for (int i = 0; i < s.length(); i++) {
                    char ati = array[i];

                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == ati)   continue;
                        array[i] = c;
                        String each = new String(array);
                        if (dict.contains(each)) {

                            if (visited.contains(each))     continue;
                            if (each.equals(end))   return count + 1;

                            q.offer(each);
                        }
                    }

                    array[i] = ati;
                }

            }

            return 0;
        }

    }


    public class Solution_recursion_over_time {
        Set<String> used = new HashSet<>();
        int min = Integer.MAX_VALUE;

        // return: 5
        public int ladderLength(String beginWord, String endWord, Set<String> wordList) {

            // @note@memorize: System.out.println(one.ladderLength("hit", "cog", new HashSet<String>(Arrays.asList("hot","dot","dog","lot","log"))));
            if (beginWord == null || beginWord.length() == 0 || endWord == null || endWord.length() == 0) {
                return 0;
            }

            // @note: test on char
            // System.out.println('a' + 1); // output: 98
            // System.out.println((char)('a' + 1)); // output: b

            used.add(beginWord); // @note: dont forget adding it
            wordList.add(endWord); // @note: dont forget !!! when checking one-step-word validity, endWord should be valid...
            findLadder(beginWord, endWord, wordList, 0); // begin and end are same, then length==0

            return min;
        }

        private void findLadder(String beginWord, String endWord, Set<String> wordList, int count) {

            if (beginWord.equals(endWord)) {
                min = Math.min(min, count);

                return;
            }

            List<String> all = getWordsOneStepAndInDict(beginWord, wordList);

            // System.out.println(all.toString());

            if (all.size() == 0) {
                return;
            }

            for (int i = 0; i < all.size(); i++) {

                String next = all.get(i);

                used.add(next);
                findLadder(next, endWord, wordList, count + 1);
                // used.remove(used.size() - 1); // @note:@memorize: HashSet is not remove(index), but remove(object)
                used.remove(used.size() - 1);
            }
        }

        private boolean isValidWord(String w, Set<String> wordList) {
            return wordList.contains(w) && !used.contains(w);
        }

        private List<String> getWordsOneStepAndInDict(String w, Set<String> wordList) {

            List<String> result = new ArrayList<>(); // 26 chars, except itself

            // length * 26, still o(n) though
            for (int pos = 0; pos < w.length(); pos++) {
                for (int i = 0; i <= 25; i++) {

                    char newChar = (char)('a' + i);

                    if (w.charAt(pos) != newChar) {

                        String one = w.substring(0, pos) + newChar + w.substring(pos + 1);

                        if (isValidWord(one, wordList)) { // @note: important, avoid infinite looping
                            result.add(one);
                        }
                    }
                }
            }

            return result;
        }
    }

}

All Problems

All Solutions