127. Word Ladder (Medium)

https://leetcode.com/problems/word-ladder/

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 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.

Solutions

class Solution {

    // Do not pairwise calculate the edit distance of words present in wordList, there is a good change to
    // bring about the issue of computation overhead.

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList == null || wordList.size() == 0) {
            return 0;
        }

        if (beginWord.equals(endWord)) {
            return 1;
        }

        // FIXME Convert List to Set, otherwise time limit exceed occurs.
        Set<String> dict = new HashSet<>(wordList);

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        // Initialize the startup state
        queue.offer(beginWord);
        visited.add(beginWord);

        int ans = 1;

        while (!queue.isEmpty()) {

            ans++;

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

                String curr = queue.poll();

                List<String> adjacentWords = findAdjacent(curr, dict, visited);

                // BFS all the one step transformed words
                for (String word : adjacentWords) {

                    // exit of the loop
                    if (word.equals(endWord)) {
                        return ans;
                    }

                    queue.add(word);
                    visited.add(word);
                }
            }
        }

        // Once reach here, no such possible transformation sequence is found.

        return 0;
    }

    private List<String> findAdjacent(String word, Set<String> dict, Set<String> visited) {

        // Sort out all possible transformations of the given word by change on letter.
        // Any new words not visited yet but present in the word dictionary will be adopted.

        List<String> adjacentWords = new ArrayList<>();

        for (int i = 0; i < word.length(); i++) {
            for (char j = 'a'; j <= 'z'; j++) {
                if (j == word.charAt(i)) {
                    continue;
                }

                String newWord = transform(word, i, j);
                if (visited.contains(newWord)) {
                    continue;
                }

                if (dict.contains(newWord)) {
                    adjacentWords.add(newWord);
                }
            }
        }

        return adjacentWords;
    }

    private String transform(String word, int idx, Character rc) {
        String ans = "";
        for (int i = 0; i < word.length(); i++) {
            ans += (i == idx) ? rc : word.charAt(i);
        }

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""