面试题 17.22. 单词转换
题目
给定字典中的两个词,长度相等。写一个方法,把一个词转换成另一个词, 但是一次只能改变一个字符。 每一步得到的新词都必须能在字典中找到。
编写一个程序,返回一个可能的转换序列。如有多个可能的转换序列,你可以返回任何一个。
示例 1: 输入: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] 输出: [“hit”,”hot”,”dot”,”lot”,”log”,”cog”]
示例 2:
输入: beginWord = “hit” endWord = “cog” wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
输出: []
解释: endWord “cog” 不在字典中,所以不存在符合要求的转换序列。
题解
public List<String> findLadders(String beginWord, String endWord, List<String> wordList) {
Set<String> words = new HashSet<>(wordList);
// 开始单词或结束单词不存在与字典中
if (!words.contains(endWord)) {
return Collections.emptyList();
}
// 是否满足转换条件 两个单词只能有一个字母不同
BiPredicate<String, String> isCondition = (s, t) -> {
int len = s.length(), cnt = 0;
for (int i = 0; i < len; i++) {
if (s.charAt(i) != t.charAt(i)) {
cnt++;
if (cnt > 1) {
return false;
}
}
}
return cnt == 1;
};
List<String> result = new ArrayList<>(), dict = new ArrayList<>(words);
int len = dict.size();
// 标记已经使用过的单词
int[] visited = new int[len];
Function<String, Boolean> backtrack = new Function<String, Boolean>() {
@Override
public Boolean apply(String prefix) {
result.add(prefix);
if (Objects.equals(prefix, endWord)) {
return true;
}
for (int i = 0; i < len; i++) {
String word = dict.get(i);
if (visited[i] == 0 && isCondition.test(prefix, word)) {
visited[i] = 1;
Boolean apply = this.apply(word);
// 找到解 直接结束
if (apply) {
return true;
}
// 回溯
result.remove(result.size() - 1);
}
}
return false;
}
};
if (backtrack.apply(beginWord)) {
return new ArrayList<>(result);
}
return Collections.emptyList();
}