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 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);
}
}
}
}
}
}
}