Word Ladder
lc 127
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 intermediate word must exist in the word list
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
解题报告： 针对这一道题，bfs就可以给出比较optimal 的方法，bfs找出每一步能实现的单词，然后找到最短路径。
time complexity: for getNext ,the complexity is O(m26), o(n m) space o(n)
解法2019
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (wordList.size() == 0 || !wordList.contains(endWord)) return 0;
Set<String> dictSet = new HashSet<>(wordList);
Set<String> set = new HashSet<>();
Queue<String> queue = new LinkedList<>();
int result = 0;
queue.offer(beginWord);
set.add(beginWord);
while (!queue.isEmpty()) {
result++;
List<String> list = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
String cur = queue.poll();
if (cur.equals(endWord)) return result;
List<String> nextWords = getNextWords(cur, dictSet);
for (String word: nextWords) {
if (!set.contains(word)) {
set.add(word);
list.add(word);
}
}
}
queue.addAll(list);
}
return 0;
}
List<String> getNextWords(String start, Set<String> wordList) {
List<String> res = new ArrayList<>();
for (int i = 0; i < start.length(); i++) {
for (char j = 'a'; j <= 'z'; j++) {
if (start.charAt(i) == j) continue;
StringBuilder sb = new StringBuilder();
sb.append(start.substring(0, i));
sb.append(j);
sb.append(start.substring(i + 1));
if (wordList.contains(sb.toString())) {
res.add(sb.toString());
}
}
}
return res;
}
}
public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
if ( wordList == null ) return 0;
if ( beginWord.equals(endWord)) return 0;
//
//wordList.add(beginWord);
wordList.add(endWord);
HashSet<String> hash = new HashSet<String>();
Queue<String> queue = new LinkedList<String>();
queue.offer(beginWord);
hash.add(beginWord);
int result = 1;
while ( ! queue.isEmpty()){
result++;
int size = queue.size();
for(int i = 0 ; i < size; i++){
String word = queue.poll();
for ( String nextWord : getNextWords(word, wordList)){
if (hash.contains(nextWord)){
continue;
}
if (nextWord.equals(endWord)){
return result;
}
hash.add(nextWord);
queue.offer(nextWord);
}
}
}
return 0;
}
public ArrayList<String> getNextWords(String word, Set<String> wordList){
ArrayList<String> result = new ArrayList<String>();
for ( char c = 'a'; c <= 'z'; c++){
for (int i = 0 ; i < word.length(); i++){
if (word.charAt(i) == c) {
continue;
}
String nextWord = replace(word, c, i);
if (wordList.contains(nextWord)){
result.add(nextWord);
}
}
}
return result;
}
public String replace(String word, char c, int position){
char[] chars = word.toCharArray();
chars[position] = c;
return new String(chars);
}
}
wordLadder II
lc 126
return all of possible solutions. shortest path
The basic idea is:
1). Use BFS to find the shortest distance between start and end, tracing the distance of crossing nodes from start node to end node, and store node's next level neighbors to HashMap;
2). Use DFS to output paths with the same distance as the shortest distance from distance HashMap: compare if the distance of the next level node equals the distance of the current node + 1.
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
HashSet<String> dict = new HashSet<String>(wordList);
List<List<String>> ladders = new ArrayList<List<String>>();
Map<String, List<String>> nodeNeighbors = new HashMap<>();
Map<String, Integer> distance = new HashMap<>();
dict.add(beginWord);
List<String> path = new ArrayList<>();
bfs(beginWord, endWord, dict, nodeNeighbors, distance);
path.add(beginWord);
dfs(beginWord, endWord, dict, nodeNeighbors, distance, path, ladders);
return ladders;
}
private void bfs(String beginWord, String endWord, HashSet<String> wordList, Map<String, List<String>> nextWordsMap, Map<String, Integer> distance) {
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
distance.put(beginWord, 0);
for (String s : wordList) {
nextWordsMap.put(s, new ArrayList<String>());
}
//int count = 0;
boolean findMin = false;
while (!queue.isEmpty()) {
//count++;
int size = queue.size();
for (int i = 0; i < size; i++) {
String cur = queue.poll();
List<String> nextList = getNextWords(cur, wordList);
for (String next: nextList) {
nextWordsMap.get(cur).add(next);
if (!distance.containsKey(next)) {
distance.put(next, distance.get(cur) + 1);
queue.offer(next);
}
if (next.equals(endWord)) {
findMin = true;
}
}
}
if (findMin){
break;
}
}
}
private void dfs(String beginWord, String endWord, HashSet<String> wordList, Map<String, List<String>> nextWordsMap, Map<String, Integer> distance, List<String> path, List<List<String>> ladders) {
if (beginWord.equals(endWord)) {
ladders.add(new ArrayList<>(path));
return;
}
for(String s : nextWordsMap.get(beginWord)) {
if (distance.get(s) == distance.get(beginWord) + 1) {
path.add(s);
dfs(s, endWord, wordList, nextWordsMap, distance, path, ladders);
path.remove(path.size() - 1);
}
}
}
private List<String> getNextWords(String crt, HashSet<String> dict) {
List<String> nextWords = new ArrayList<String>();
for (int i = 0; i < crt.length(); i++) {
for (char ch = 'a'; ch <= 'z'; ch++) {
if (ch != crt.charAt(i)) {
String nextWord = crt.substring(0, i) + ch
+ crt.substring(i + 1);
if (dict.contains(nextWord)) {
nextWords.add(nextWord);
}
}
}
}
return nextWords;
}
}
错误解法 直接用dfs 超时了
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
List<List<String>> res = new ArrayList<>();
if (wordList.size() == 0 || beginWord.length() != endWord.length() || !wordList.contains(endWord)) return res;
if (!wordList.contains(beginWord)){
wordList.add(beginWord);
}
List<String> curList = new ArrayList<>();
curList.add(beginWord);
helper(res, beginWord, endWord, wordList, curList);
return res;
}
public void helper(List<List<String>> res, String beginWord, String endWord, List<String> wordList, List<String> curList) {
if (beginWord.equals(endWord)) {
if (res.size() == 0) {
res.add(new ArrayList<>(curList));
} else if (res.get(0).size() == curList.size()){
res.add(new ArrayList<>(curList));
} else if (res.get(0).size() > curList.size()) {
res.clear();
res.add(new ArrayList<>(curList));
}
return;
}
if (res.size() != 0 && res.get(0).size() < curList.size()) return;
for (int i = 0; i < beginWord.length(); i++) {
for (char j = 'a'; j <= 'z'; j++) {
if (beginWord.charAt(i) == j) continue;
StringBuilder sb = new StringBuilder();
sb.append(beginWord.substring(0, i));
sb.append(j);
sb.append(beginWord.substring(i + 1));
String cur = sb.toString();
if (curList.contains(cur) || !wordList.contains(cur)) continue;
curList.add(cur);
helper(res, cur, endWord, wordList, curList);
curList.remove(curList.size() - 1);
}
}
}
}