126. Word Ladder II

Difficulty : Hard

Related Topics : BFS、Backtracking、String、Array

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) 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 an empty list 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:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]
Example 2:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: []

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Solution

mine

Java

DFS Time Limit Exceeded

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    List<List<String>> res = new ArrayList<>();
    if (!wordList.contains(endWord)) {
        return res;
    }
    int len = beginWord.length();
    wordList.add(beginWord);
    Map<String, List<String>> map = new HashMap<>();
    for (String word : wordList) {
        for (int i = 0; i < len; i++) {
            String key = word.substring(0, i) + "*" + word.substring(i + 1);
            List<String> v = map.getOrDefault(key, new ArrayList<>());
            v.add(word);
            map.put(key, v);
        }
    }
    LinkedList<String> linkedList = new LinkedList<>();
    linkedList.add(beginWord);
    HashSet<String> visited = new HashSet<>();
    dfs(map, linkedList, visited, endWord, res);
    return res;
}


void dfs(Map<String, List<String>> map, LinkedList<String> list, HashSet<String> visited, String endWord, List<List<String>> res) {
    String cur = list.getLast();
    visited.add(cur);
    if (res.size() > 0 && list.size() + 1 > res.get(0).size()) {
        return;
    }
    for (int i = 0; i < cur.length(); i++) {
        String key = cur.substring(0, i) + "*" + cur.substring(i + 1);
        List<String> nexts = map.get(key);
        if (nexts.contains(endWord)) {
            if (res.size() > 0 && list.size() + 1 < res.get(0).size()) {
                res.clear();
            }
            List<String> temp = new ArrayList<>(list);
            temp.add(endWord);
            res.add(temp);
            continue;
        }
        for (String next : nexts) {
            if (visited.contains(next)) {
                continue;
            }
            list.add(next);
            dfs(map, list, visited, endWord, res);
            list.remove(next);
            visited.remove(next);
        }
    }
}

the most votes

Runtime: 176 ms, faster than 41.71%, Memory Usage: 47.6 MB, less than 48.10% of Java online submissions

public List<List<String>> findLadders(String start, String end, List<String> wordList) {
    HashSet<String> dict = new HashSet<>(wordList);
    List<List<String>> res = new ArrayList<>();
    HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<>();// Neighbors for every node
    HashMap<String, Integer> distance = new HashMap<>();// Distance of every node from the start node
    ArrayList<String> solution = new ArrayList<String>();

    dict.add(start);
    bfs(start, end, dict, nodeNeighbors, distance);
    dfs(start, end, dict, nodeNeighbors, distance, solution, res);
    return res;
}

// BFS: Trace every node's distance from the start node (level by level).
private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) {
    for (String str : dict)
        nodeNeighbors.put(str, new ArrayList<String>());

    Queue<String> queue = new LinkedList<String>();
    queue.offer(start);
    distance.put(start, 0);

    while (!queue.isEmpty()) {
        int count = queue.size();
        boolean foundEnd = false;
        for (int i = 0; i < count; i++) {
            String cur = queue.poll();
            int curDistance = distance.get(cur);
            ArrayList<String> neighbors = getNeighbors(cur, dict);

            for (String neighbor : neighbors) {
                nodeNeighbors.get(cur).add(neighbor);
                if (!distance.containsKey(neighbor)) {// Check if visited
                    distance.put(neighbor, curDistance + 1);
                    if (end.equals(neighbor))// Found the shortest path
                        foundEnd = true;
                    else
                        queue.offer(neighbor);
                }
            }
        }
        if (foundEnd)
            break;
    }
}

// Find all next level nodes.
private ArrayList<String> getNeighbors(String node, Set<String> dict) {
    ArrayList<String> res = new ArrayList<String>();
    char[] chs = node.toCharArray();

    for (char ch = 'a'; ch <= 'z'; ch++) {
        for (int i = 0; i < chs.length; i++) {
            if (chs[i] == ch) continue;
            char old_ch = chs[i];
            chs[i] = ch;
            if (dict.contains(String.valueOf(chs))) {
                res.add(String.valueOf(chs));
            }
            chs[i] = old_ch;
        }

    }
    return res;
}

// DFS: output all paths with the shortest distance.
private void dfs(String cur, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) {
    solution.add(cur);
    if (end.equals(cur)) {
        res.add(new ArrayList<String>(solution));
    } else {
        for (String next : nodeNeighbors.get(cur)) {
            if (distance.get(next) == distance.get(cur) + 1) {
                dfs(next, end, dict, nodeNeighbors, distance, solution, res);
            }
        }
    }
    solution.remove(solution.size() - 1);
}

the leetcode solution

Runtime: 638 ms, faster than 18.50%, Memory Usage: 54.9 MB, less than 14.03% of Java online submissions

// O(N^2 * len)time   len = word.length
// O(N^2)space
private static final int INF = 1 << 20;
private Map<String, Integer> wordId = new HashMap<>();
private ArrayList<String> idWord = new ArrayList<>();
private ArrayList<Integer>[] edges;

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    int id = 0;
    //define a id for each distinct word
    for (String word : wordList) {
        if (!wordId.containsKey(word)) { 
            wordId.put(word, id++);
            idWord.add(word);
        }
    }

    if (!wordId.containsKey(endWord)) {
        return new ArrayList<>();
    }
   
    if (!wordId.containsKey(beginWord)) {
        wordId.put(beginWord, id++);
        idWord.add(beginWord);
    }
    
    edges = new ArrayList[idWord.size()];
    for (int i = 0; i < idWord.size(); i++) {
        edges[i] = new ArrayList<>();
    }
    
    for (int i = 0; i < idWord.size(); i++) {
        for (int j = i + 1; j < idWord.size(); j++) {
            if (transformCheck(idWord.get(i), idWord.get(j))) {
                edges[i].add(j);
                edges[j].add(i);
            }
        }
    }

    int dest = wordId.get(endWord); // dst ID
    List<List<String>> res = new ArrayList<>();
    int[] cost = new int[id];
    for (int i = 0; i < id; i++) {
        cost[i] = INF;
    }

    Queue<ArrayList<Integer>> q = new LinkedList<>();
    ArrayList<Integer> tmpBegin = new ArrayList<>();
    tmpBegin.add(wordId.get(beginWord));
    q.add(tmpBegin);
    cost[wordId.get(beginWord)] = 0;
    
    while (!q.isEmpty()) {
        ArrayList<Integer> now = q.poll();
        int last = now.get(now.size() - 1);
        if (last == dest) {
            ArrayList<String> tmp = new ArrayList<>();
            for (int index : now) {
                tmp.add(idWord.get(index));
            }
            res.add(tmp);
        } else {
            for (int i = 0; i < edges[last].size(); i++) {
                int to = edges[last].get(i);
                if (cost[last] + 1 <= cost[to]) {
                    cost[to] = cost[last] + 1;
                    ArrayList<Integer> tmp = new ArrayList<>(now); tmp.add(to);
                    q.add(tmp);
                }
            }
        }
    }
    return res;
}

boolean transformCheck(String str1, String str2) {
    int differences = 0;
    for (int i = 0; i < str1.length() && differences < 2; i++) {
        if (str1.charAt(i) != str2.charAt(i)) {
            ++differences;
        }
    }
    return differences == 1;
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

126. Word Ladder II.md

126. Word Ladder II.md

126. Word Ladder II

Note:

Example 1:

Example 2:

Solution

Files

126. Word Ladder II.md

Latest commit

History

126. Word Ladder II.md

File metadata and controls

126. Word Ladder II

Note:

Example 1:

Example 2:

Solution