Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:
For 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.
解题思路一：
对set进行逐个遍历，递归实现，JAVA实现如下：
static public int ladderLength(String beginWord, String endWord,
Set<String> wordDict) {
int result = wordDict.size() + 2;
Set<String> set = new HashSet<String>(wordDict);
if (oneStep(beginWord, endWord))
return 2;
for (String s : wordDict) {
if (oneStep(beginWord, s)) {
set.remove(s);
int temp = ladderLength(s, endWord, set);
if (temp != 0)
result = Math.min(result, temp + 1);
set.add(s);
}
}
if (result == wordDict.size() + 2)
return 0;
return result;
}
public static boolean oneStep(String s1, String s2) {
int res = 0;
for (int i = 0; i < s1.length(); i++)
if (s1.charAt(i) != s2.charAt(i))
res++;
return res == 1;
}
结果TLE
解题思路二：
Java for LeetCode 127 Word Ladder
原文：http://www.cnblogs.com/tonyluis/p/4532839.html