leetcode 126. Word Ladder II ----- java

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

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

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["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.

从start变换到end,途中只能经过字典中的单词,每次只允许差一个字母。
要求输出所有最短变换路径。

这里刚开始使用了最普通的方法,即利用DFS,超时了。

public class Solution {

    List list = new ArrayList<List>();
int num = 0;
String[] words;
String[] ans;
public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) { if( beginWord.length() == 0 || wordList.size() == 0 )
return list;
int len = wordList.size();
words = new String[len];
int i = 0;
for( String str : wordList ){
words[i] = str;
i++;
}
ans = new String[len+2];
ans[0] = beginWord; helper(beginWord,endWord,1);
return list; } public void helper(String beginWord,String endWord,int pos){ if( OneDiff(beginWord,endWord)){
if( num == 0 )
num = pos;
else if( num < pos )
return;
else if( num > pos ){
list.clear();
num = pos;
}
List ll = new ArrayList<String>();
for( int i = 0;i<pos;i++)
ll.add(ans[i]);
ll.add(endWord);
list.add(ll);
return ;
} for( int i = 0;i<words.length;i++){
String str = words[i];
if( str == "-1")
continue;
if( OneDiff(beginWord,str) ){
ans[pos] = str;
words[i] = "-1";
helper(str,endWord,pos+1);
words[i] = str;
}
} } public boolean OneDiff(String word1,String word2){
int flag = 0;
for( int i = 0;i<word1.length();i++){ if( word1.charAt(i) == word2.charAt(i) )
continue;
else{
if( flag == 0)
flag =1;
else
return false;
} }
return true;
}
}
}

2、使用BFS,仍旧超时了。

public class Solution {

    List list = new ArrayList<List>();
Queue queue;
HashMap map = new HashMap<String,Integer>(); public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) { if( beginWord.length() == 0 || wordList.size() == 0 )
return list;
queue = new LinkedList<ArrayList<String>>();
if( OneDiff(beginWord,endWord) ){
List ll = new ArrayList<String>();
ll.add(beginWord);
ll.add(endWord);
list.add(ll);
return list;
}
List ll = new ArrayList<String>();
ll.add(beginWord);
int flag = 0;
int deep = 0;
map.put(beginWord,deep);
queue.add(ll);
while( !queue.isEmpty() ){
deep++;
int len = queue.size();
for( int i = 0;i<len;i++) {
List l1 = (List) queue.poll();
String s1 = (String) l1.get(l1.size() - 1);
for (String str : wordList) {
if (OneDiff(s1, str) && ( !map.containsKey(str) || (int)map.get(str) == deep) ) {
map.put(str,deep);
List l2 = new ArrayList<String>();
l2.addAll(l1);
l2.add(str);
queue.add(l2);
if (OneDiff(str, endWord)) {
l2.add(endWord);
// for (int ii = 0; ii < l2.size(); ii++)
// System.out.print(l2.get(ii) + " ");
// System.out.println();
list.add(l2);
flag = 1;
}
}
}
}
if( flag == 1)
queue.clear();
}
return list; }
public boolean OneDiff(String word1,String word2){
int flag = 0;
for( int i = 0;i<word1.length();i++){ if( word1.charAt(i) == word2.charAt(i) )
continue;
else{
if( flag == 0)
flag++;
else
return false;
} }
if( flag == 1)
return true;
else
return false;
}
}

3、借鉴了他人的答案

优化方法:先BFS生成找到end时的生成树,标记出每个单词所在的层数。然后从目标用DFS往回找,过了大数据。

NOTE:我在代码中刚开始由于存在static,导致测试用例一直无法通过。

public class Solution {

    List list = new ArrayList<List>();
HashMap map = new HashMap<String,Integer>(); public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) { if( beginWord == null || beginWord.length() == 0 || wordList.size() == 0 || beginWord.length() != endWord.length() )
return list; BFS(beginWord,endWord,wordList);
if( map.size()== 1 )
return list;
DFS(endWord,beginWord,new ArrayList<String>()); return list; }
public void DFS(String beginWord,String endWord,List ans){ if( beginWord.equals(endWord) ){
ans.add(beginWord);
Collections.reverse(ans);
list.add(ans);
return ;
}
if( map.get(beginWord) == null )
return ;
ans.add(beginWord);
int deep = (int) map.get(beginWord)-1;
for( int i = 0;i<beginWord.length();i++){
char[] word = beginWord.toCharArray();
for( char ch = 'a';ch<='z';ch++) {
word[i] = ch;
String nWord = new String(word);
if ( map.get(nWord) != null && ((int) map.get(nWord) == deep)) {
ArrayList ll = new ArrayList<String>(ans);
DFS(nWord, endWord, ll); }
}
}
}
public void BFS(String beginWord,String endWord,Set<String> wordList){ Queue queue = new LinkedList<String>();
queue.add(beginWord);
map.put(beginWord,0);
while( !queue.isEmpty() ){
String str = (String) queue.poll();
if( str.equals(endWord) )
continue;
for( int i = 0 ;i <beginWord.length();i++){
char[] word = str.toCharArray();
for( char ch = 'a';ch<='z';ch++) {
word[i] = ch;
String Nword = new String(word);
if ( Nword.equals(endWord) || wordList.contains(Nword)) {
if (!map.containsKey(Nword)) {
map.put(Nword, (int) map.get(str) + 1);
queue.add(Nword);
}
}
}
}
}
} }
上一篇:mybatis(五):源码分析 - mapper文件解析流程


下一篇:Python合并多个Excel数据