这个题还有印象。
其实是个图像题，每个Sring是个vertex，有edge到另一个vertex说明可以转化，当然要自己构建。
构建之后做一个BFS找最短路径。
BFS就一个套路，问题就在于如何判断俩单词是否可以转化。
一刷的时候我记得是看了code ganker的一个巧妙的方法。这次尝试用自己的办法，String A, String B，遍历比较不同，等于1就TRUE，否则FALSE.
结果TLE...靠，做了好久的。。
public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordList)
{
Queue<String> q = new LinkedList<String>();
Set<String> check = new HashSet<String>();
q.add(beginWord);
check.add(beginWord);
int cur = 1;
int level = 1;
int total = 0;
while(!q.isEmpty())
{
String temp = q.poll();
cur--;
String trStr = transfer(temp,wordList,check);
while(!trStr.equals(""))
{
q.add(trStr);
check.add(trStr);
if(trStr.equals(endWord))
{
return level+1;
}
total++;
trStr = new String(transfer(temp,wordList,check));
}
if(cur == 0)
{
cur = total;
total = 0;
level++;
}
}
return 0;
}
public String transfer(String str1, Set<String> wordList, Set<String> check)
{
String res = "";
Iterator iter = wordList.iterator();
while(iter.hasNext())
{
String str2 = (String)iter.next();
if(check.contains(str2))
{
continue;
}
if(isOK(str1,str2))
{
return str2;
}
}
return res;
}
public boolean isOK(String str1, String str2)
{
int i = 0;
int res = 0;
//System.out.println(str1 + " " + str2);
while(i < str1.length())
{
if(str1.charAt(i) != str2.charAt(i))
{
res++;
if(res > 1) return false;
}
i++;
}
if(res == 0) return false;
return true;
}
}
然后介绍下CODE GANKER的办法。
比如"a"，他最多能有25个edge就是"b","c","d".."z".
比如"ab",最多是"aa","ac","ad"..."bb","cb","db"..
总之一次只能改变1个字母嘛，每一位有26种选择(算上它自己)。
因为单词长度不会很长，所以可以穷举。。每位每次变一个，看在不在LIST里。。在就说明可以转化。
把中间的判断部分改一下就行了。。
public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordList)
{
Queue<String> q = new LinkedList<String>();
Set<String> check = new HashSet<String>();
q.add(beginWord);
check.add(beginWord);
int cur = 1;
int level = 1;
int total = 0;
while(!q.isEmpty())
{
String temp = q.poll();
cur--;
for(int i = 0; i < temp.length();i++)
{
char[] tempArray = temp.toCharArray();
for(char j = 'a'; j <= 'z';j++)
{
tempArray[i] = j;
String newString = new String(tempArray);
if(!check.contains(newString) && wordList.contains(newString))
{
if(newString.equals(endWord)) return level+1;
check.add(newString);
q.add(newString);
total++;
}
}
}
if(cur == 0)
{
cur = total;
total = 0;
level++;
}
}
return 0;
}
}
看一刷写的记录，我一刷居然用的DFS,然后TLE。我完全记不得当时的情况，对于当时唯一还存留的印象就是我当时的姓名和性别。
肯定有DFS的做法，介于我现在做题把头做大了(胖头鱼YYF)，就不看了。。