Word Ladder I && II

Word Ladder I  — 只需要找一条最短路

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution: BFS – BFS模板 O(n*L) n: size of dict, L: the max length of the words

visited set记录已经访问过的路 一旦找到一条就退出

注意字符串的处理

public int ladderLength(String start, String end, Set<String> dict) {
    if (dict == null || dict.size() == 0) {
        return 0;
    }
    Queue<String> queue = new LinkedList<String>();
    queue.offer(start);
    int length = 1;
    Set<String> visited = new HashSet<>();
    visited.add(start);
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String curr = queue.poll();
            for (char newChar = 'a'; newChar <= 'z'; newChar++) {
                for (int j = 0; j < start.length(); j++) {
                    if (newChar == curr.charAt(j)) {
                        continue;
                    }
                    String nextStep = curr.substring(0, j) + newChar + curr.substring(j + 1);
                    if (nextStep.equals(end)) {
                        return length + 1;
                    }
                    if (dict.contains(nextStep) && !visited.contains(nextStep)) {
                        queue.offer(nextStep);
                        visited.add(nextStep);
                    }
                }
            }
        }
        length++;
    }
    return 0;
}

Word Ladder II –找出所有最短路

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary
Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]
Note

  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

Solution: BFS+DFS

1. 先用BFS找出最短路径的长度,同时把相邻节点和每个点到起点的distance保存下来

2. 用DFS找出所有最短路径,distance超过最短路径的长度的就不用考虑了,所谓pruning.

public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    List<List<String>> result = new ArrayList<>();
    if (dict == null || dict.size() == 0) {
        return result;
    }
    List<String> curr = new ArrayList<>();
    curr.add(start);
    Map<String, Integer> distance = new HashMap<>();
    Map<String, List<String>> neighborsMap = new HashMap<>();
    int minTrans = bfs(start, end, dict, distance, neighborsMap);
    findLaddersHelper(curr, end, minTrans, distance, neighborsMap, result);
    return result;
}

public void findLaddersHelper(List<String> curr, String end, int maxStep, Map<String, Integer> distance,
                              Map<String, List<String>> neighborsMap, List<List<String>> result) {
    String currStr = curr.get(curr.size() - 1);
    if (maxStep == 0) {
        if (currStr.equals(end)) {
            result.add(new ArrayList<>(curr));
        }
        return;
    }
    for (String neighbor : neighborsMap.get(currStr)) {
        if (distance.get(neighbor) == distance.get(currStr) + 1) {
            curr.add(neighbor);
            findLaddersHelper(curr, end, maxStep - 1, distance, neighborsMap, result);
            curr.remove(curr.size() - 1);
        }
    }
}

//first use BFS to find the shortest transformation
public int bfs(String start, String end, Set<String> dict,
               Map<String, Integer> distance, Map<String, List<String>> neighborsMap) {
    Queue<String> queue = new LinkedList<>();
    queue.offer(start);
    distance.put(start, 0);
    int minTrans = -1;
    while (!queue.isEmpty()) {
        int size = queue.size();
        String str = queue.poll();
        List<String> neighbors = new ArrayList<>();
        for (char newChar = 'a'; newChar <= 'z'; newChar++) {
            for (int index = 0; index < start.length(); index++) {
                if (newChar == str.charAt(index)) {
                    continue;
                }
                String newStr = str.substring(0, index) + newChar + str.substring(index + 1);
                if (newStr.equals(end) && minTrans == -1) {
                    minTrans = distance.get(str) + 1;
                }
                if (dict.contains(newStr)) {
                    neighbors.add(newStr);
                    if (!distance.containsKey(newStr)) {
                        distance.put(newStr, distance.get(str) + 1);
                        queue.offer(newStr);
                    }
                }
            }
        }
        neighborsMap.put(str, neighbors);
    }
    return minTrans;
}
FacebookTwitterGoogle+Share