[学习交流] 发一道题目玩 0.0

本帖最后由 cat73 于 2016-7-14 19:05 编辑

给你两个单词一个作为开头一个作为结尾。
再给你一组单词作为中间单词。
请找到最短的从开头到结尾的转换路径，如果有多个路径均为最短，则均应该输出。

限制如下：
每次转换只允许变动一个字母。
只允许用中间单词里的单词来转换。

例子：

// 参数
String beginWord = "hit";
String endWord = "cog";
String[] wordList = new String[] {"hot", "dot", "dog", "lot", "log"};
// 返回值：
return new String[][] {
{"hit","hot","dot","dog","cog"},
{"hit","hot","lot","log","cog"}
};

复制代码

参数与返回值的表达形式不强制，你觉得怎么舒服这么来，重要的是算法。

cat73 · cat73

这道题的原题在这里：https://leetcode.com/problems/word-ladder-ii/
这是一个效率极低的解法，这网站的测试里居然有 599 个中间单词，这种算法直接炸，5 分钟也跑不完。。。
而这个网站好像不到 10 秒就报超时错误了。。。

public class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
// 结果
List<List<String>> results = new ArrayList<>();
// 没有中间单词就可以直接转的情况
if(hasConversion(beginWord, endWord)) {
List<String> result = new ArrayList<>();
result.add(beginWord);
result.add(endWord);
results.add(result);
return results;
}
// 中间词 Set 转为数组
String[] wordArray = wordList.toArray(new String[] {});
// 按照中间单词数循环，如果在某个长度找到了可以转换的路径，则不再尝试下一个长度
for(int len = 1; len <= wordList.size() && results.size() == 0; len++) {
// 数字迭代器
Iterator<Integer[]> it = new NumberIterator(0, wordArray.length - 1, len);
loop: while (it.hasNext()) {
// 获取下一个数字
final Integer[] num = it.next();
// 数字不能重复
for (int i = 0; i < num.length; i++) {
for (int j = 0; j < num.length; j++) {
if (i != j && num[i] == num[j]) {
continue loop;
}
}
}
// 判断头到第一个中间词能否转换
if(!hasConversion(beginWord, wordArray[num[0]])) {
continue loop;
}
// 判断两个中间词之间能否转换
for (int i = num.length - 1; i > 0; i--) {
if(!hasConversion(wordArray[num[i]], wordArray[num[i - 1]])) {
continue loop;
}
}
// 判断最后一个中间词到尾能否转换
if(!hasConversion(wordArray[num[num.length - 1]], endWord)) {
continue loop;
}
// 保存结果
List<String> result = new ArrayList<>();
result.add(beginWord);
for (int i = 0; i < num.length; i++) {
result.add(wordArray[num[i]]);
}
result.add(endWord);
results.add(result);
}
}
return results;
}
private boolean hasConversion(String formWord, String toWord) {
for(int i = 0, difference = 0; i < formWord.length(); i++) {
if(formWord.charAt(i) != toWord.charAt(i)) {
difference += 1;
if(difference > 1) {
return false;
}
}
}
return true;
}
/**
* 一个数字的迭代器
* 可通过 next 返回一个 Integer 数组，每一个元素代表在这一位上的数字，返回值是大端序的
* 此实现不是多线程安全的
* 最大可描述不大于 2 ^ 32 进制、不长于 Integer.MAX_VALUE 位的所有数字
*
* @author Cat73
*/
public class NumberIterator implements Iterator<Integer[]> {
private final int min;
private final int max;
private final int length;
private boolean hasNext = true;
private final Integer[] number;
/**
* 构造一个新的数字迭代器
*
* @param min 每个位上的数字最小是多少？
* @param max 每个位上的数字最大是多少？
* @param length 这个数字有多长？
* @throws RuntimeException 如果 min > max
*/
public NumberIterator(final int min, final int max, final int length) {
// 输入检查
if (min > max) {
throw new RuntimeException("max: " + max + ", min: " + min);
} else if (length < 1) {
this.hasNext = false;
}
// 初始化属性
this.min = min;
this.max = max;
this.length = length;
this.number = new Integer[this.length];
// 初始化值到最小值
for (int i = 0; i < this.length; i++) {
this.number[i] = this.min;
}
}
@Override
public Integer[] next() {
// 如果没有下一个元素则抛出异常
if (!this.hasNext) {
throw new java.util.NoSuchElementException();
}
// 将当前数值当做结果
final Integer[] result = Arrays.copyOf(this.number, this.length);
// 将数字加 1
this.number[0] += 1;
for (int i = 0; i < this.length && this.number[i] > this.max; i++) {
// 如果无法再进位则视为没有下一个元素
if (i + 1 >= this.length) {
this.hasNext = false;
} else {
this.number[i] = this.min;
this.number[i + 1] += 1;
}
}
// 返回当前元素
return result;
}
@Override
public boolean hasNext() {
return this.hasNext;
}
}
}

复制代码

cat73 · cat73

首先想到的就是这种遍历了，结果时间太长。
然后想到多叉树展开的方案，结果内存开销太大，时间还是太长，有大量重复的部分而且很难剪枝。。
我再想想别的方案。。。

cat73 · cat73

599 个 3 个字母的单词的过了，分享下代码（请自行删除 Timing 相关的代码）：
接下来是 4565 个 5 个字母的单词。。。
在我的本本上 850ms 跑完。。。
然而还是超时。。。

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class WordLadderII {
/**
* 判断两个单词之间能否进行转换
*
* @param formWord 源单词
* @param toWord 目标单词
* @return 能否进行转换
*/
private boolean hasConversion(final String formWord, final String toWord) {
int difference = 0;
for (int i = 0; i < formWord.length(); i++) {
if (formWord.charAt(i) != toWord.charAt(i)) {
difference += 1;
if (difference > 1) {
return false;
}
}
}
return difference == 1;
}
/**
* 寻找最短的转换路径
*
* @param beginWord 开头单词
* @param endWord 结尾单词
* @param wordList 中间单词
* @return 最短路径列表
*/
public List<List<String>> findLadders(final String beginWord, final String endWord, final Set<String> wordList) {
// 结果
final List<List<String>> results = new ArrayList<>();
// 初始化 Cache
Main.cacheTiming.startTiming();
// 单词转换关系 Cache
final Map<String, Set<String>> conversionCaches = new HashMap<>();
// 添加所有单词(含首尾单词)
conversionCaches.put(beginWord, new HashSet<>());
conversionCaches.put(endWord, new HashSet<>());
for (final String word : wordList) {
conversionCaches.put(word, new HashSet<>());
}
// 初始化每个单词可以转换到的单词列表
for (final String key1 : conversionCaches.keySet()) {
final Set<String> conversionCache = conversionCaches.get(key1);
for (final String key2 : conversionCaches.keySet()) {
if (this.hasConversion(key1, key2)) {
conversionCache.add(key2);
}
}
}
Main.cacheTiming.stopTiming();
// 核心算法
Main.algorithmTiming.startTiming();
// 上一层的节点列表
List<TreeNode<String>> lastNodes = new ArrayList<>();
lastNodes.add(new TreeNode<>(beginWord));
// 已经遍历过的单词列表(用于去除循环引用)
Set<String> lastKeys = new HashSet<>(conversionCaches.size());
lastKeys.add(beginWord);
// 按照中间单词数循环，如果在某个长度找到了可以转换的路径，则不再尝试下一个长度
for (int len = 1; len <= wordList.size() + 1 && results.size() == 0; len++) {
// 当前层节点列表
List<TreeNode<String>> currentNodes = new ArrayList<>(conversionCaches.size() - lastKeys.size());
// 当前层使用过的单词列表
Set<String> currentKeys = new HashSet<>(conversionCaches.size() - lastKeys.size());
// 展开上一层树
for(TreeNode<String> node : lastNodes) {
// 从缓存中读取当前节点的子节点列表
for(String word : conversionCaches.get(node.getValue())) {
// 如果为结果则加入结果列表
if(word.equals(endWord)) {
List<String> result = new ArrayList<>();
result.add(endWord);
TreeNode<String> current = node;
do {
result.add(current.getValue());
} while((current = current.getParentNode()) != null);
Collections.reverse(result);
results.add(result);
} else {
// 如果是未使用过的单词则加入节点列表
if(!lastKeys.contains(word)) {
currentNodes.add(node.addChildNode(new TreeNode<>(word)));
currentKeys.add(word);
}
}
}
}
// 更新上一层节点与使用过的单词的数据
lastNodes = currentNodes;
lastKeys.addAll(currentKeys);
}
Main.algorithmTiming.stopTiming();
// 返回结果
return results;
}
/**
* 多叉树节点
* 一个节点不应该同时属于多个父节点
* getParentNode 仅返回最后一次被添加到的父节点
*
* @author cat73
*/
public class TreeNode<T> {
/**
* 当前节点的值
*/
private final T value;
/**
* 父节点
*/
private TreeNode<T> parentNode;
/**
* 子节点列表
*/
private List<TreeNode<T>> childNodes;
/**
* 构造一个多叉树节点
*
* @param value 当前节点的值
*/
public TreeNode(final T value) {
this.value = value;
}
/**
* 获取当前节点的值
*
* @return 当前节点的值
*/
public T getValue() {
return this.value;
}
/**
* 获取父节点
*
* @return parentNode 当前节点所属的父节点
*/
public TreeNode<T> getParentNode() {
return this.parentNode;
}
/**
* 添加子节点
*
* @param childNode 要被添加的子节点
*/
public TreeNode<T> addChildNode(final TreeNode<T> childNode) {
if(this.childNodes == null) {
this.childNodes = new ArrayList<>();
}
this.childNodes.add(childNode);
childNode.parentNode = this;
return childNode;
}
}
}

复制代码

cat73 · cat73

本帖最后由 cat73 于 2016-7-15 11:33 编辑

重新思考了一下，只要一个节点允许多个父节点，那么缓存根本就没必要，而且可以砍掉一大半转换。
结果只要从 END 节点向前递归就可以了。

这算法 4565 个中间单词在我的电脑上展开树需要 400ms。。。
之前的算法创建缓存 800ms+，展开树 50ms。。。

cat73 · cat73

5 个字符长度的单词，4565 个中间单词的测试过了，在我的电脑上大概 400ms 左右，分享下代码：

中间单词数: 4565
总耗时: 387.973248ms
展开树耗时: 386.685609ms
拼接结果耗时: 0.390396ms
临时测试代码算法耗时: 0.0ms
临时测试计数器: 0
[nanny, canny, candy, sandy, sands, sends, seeds, sleds, slews, clews, clefs, cleft, cleat, bleat, bloat, float, flout, clout, cloud, aloud]
[nanny, danny, dandy, sandy, sands, sends, seeds, sleds, slews, clews, clefs, cleft, cleat, bleat, bloat, float, flout, clout, cloud, aloud]
end

复制代码

public class Solution {
private List<List<String>> results;
private List<String> result;
/**
* 寻找最短的转换路径
*
* @param beginWord 开头单词
* @param endWord 结尾单词
* @param wordList 中间单词列表
* @return 最短路径列表
*/
public List<List<String>> findLadders(final String beginWord, final String endWord, final Set<String> wordList) {
// 结果
this.results = new ArrayList<>();
//Main.expandTreeTiming.startTiming();
// 最大展开次数
int maxLen = wordList.size() + 1;
// 移除与开头单词重复的中间单词
wordList.remove(beginWord);
// 将结尾单词添加到单词列表
wordList.add(endWord);
// 上一级节点列表
Map<String, TreeNode<String>> lastNodes = new HashMap<>(1);
// 将首个单词加入
lastNodes.put(beginWord, new TreeNode<>(beginWord));
// 按照中间单词数循环，如果在某个长度找到了可以转换的路径，则不再尝试下一个长度
int len = 1;
while(!lastNodes.containsKey(endWord) && len <= maxLen) {
// 当前级节点列表
Map<String, TreeNode<String>> currentNodes = new HashMap<>();
// 展开上一级树
for (final TreeNode<String> node : lastNodes.values()) {
String word = node.getValue();
// 遍历未使用过的单词
for (final String key : wordList) {
// 如果两个单词可以互相转换
if (this.hasConversion(word, key)) {
// 如果已经存在这个单词，则在其所属节点增加一个父节点，否则新建一个子节点
if(currentNodes.containsKey(key)) {
node.addChildNode(currentNodes.get(key));
} else {
TreeNode<String> keyNode = new TreeNode<>(key);
node.addChildNode(keyNode);
currentNodes.put(key, keyNode);
}
}
}
}
// 用当前级节点列表覆盖上一级节点列表
lastNodes = currentNodes;
// 移除已使用过的中间单词
wordList.removeAll(currentNodes.keySet());
// 继续搜寻更长的路径
len += 1;
}
// Main.expandTreeTiming.stopTiming();
// Main.resultTiming.startTiming();
TreeNode<String> endNode = lastNodes.get(endWord);
if(endNode != null) {
this.result = new ArrayList<>(len);
this.result.add(endWord);
for(int i = 1; i < len; i++) {
this.result.add(null);
}
this.addResults(endNode.getParentNodes().iterator(), 1);
}
// Main.resultTiming.stopTiming();
// 返回结果
return this.results;
}
private void addResults(Iterator<TreeNode<String>> it, int index) {
while(it.hasNext()) {
TreeNode<String> node = it.next();
this.result.set(index, node.getValue());
List<TreeNode<String>> parentList = node.getParentNodes();
if(parentList.isEmpty()) {
List<String> result = new ArrayList<>(this.result);
Collections.reverse(result);
this.results.add(result);
} else {
addResults(parentList.iterator(), index + 1);
}
}
}
/**
* 判断两个单词之间能否进行转换
*
* @param formWord 源单词
* @param toWord 目标单词
* @return 能否进行转换
*/
private boolean hasConversion(final String formWord, final String toWord) {
for (int i = formWord.length() - 1, difference = 0; i >= 0; i--) {
if (formWord.charAt(i) != toWord.charAt(i)) {
difference += 1;
if (difference > 1) {
return false;
}
}
}
return true;
}
// =============
/**
* 多叉树节点
*
* @author cat73
*/
public class TreeNode<T> {
/**
* 当前节点的值
*/
private final T value;
/**
* 父节点列表
*/
private List<TreeNode<T>> parentNode;
/**
* 子节点列表
*/
private List<TreeNode<T>> childNodes;
/**
* 构造一个多叉树节点
*
* @param value 当前节点的值
*/
public TreeNode(final T value) {
this.value = value;
}
/**
* 获取当前节点的值
*
* @return 当前节点的值
*/
public T getValue() {
return this.value;
}
/**
* 获取父节点列表
*
* @return parentNode 当前节点所属的父节点列表
*/
public List<TreeNode<T>> getParentNodes() {
if (this.parentNode == null) {
this.parentNode = new ArrayList<>();
}
return this.parentNode;
}
/**
* 添加一个父节点
*
* @param childNode 要被添加的父节点
*/
private void addParentNode(TreeNode<T> parentNode) {
if (this.parentNode == null) {
this.parentNode = new ArrayList<>();
}
this.parentNode.add(parentNode);
}
/**
* 获取子节点列表
*
* @return parentNode 当前节点所属的父节点列表
*/
public List<TreeNode<T>> getChildNodes() {
if (this.childNodes == null) {
this.childNodes = new ArrayList<>();
}
return this.childNodes;
}
/**
* 添加子节点(会同时在子节点增加父节点)
*
* @param childNode 要被添加的子节点
*/
public void addChildNode(final TreeNode<T> childNode) {
if (this.childNodes == null) {
this.childNodes = new ArrayList<>();
}
this.childNodes.add(childNode);
childNode.addParentNode(this);
}
}
}

复制代码

cat73 · cat73

本帖最后由 cat73 于 2016-7-15 12:29 编辑

接下来是 6 个字符长，2623 个中间单词的测试，在我的电脑上只需要 150ms 左右，然而还是报超时错误。。
看来是时间限制更严格了。。。
我大概是理解为什么这道题这么少人过了。。。
=====
加了点代码去测试它的服务器性能。
在我的本本上 400ms 的算法，在它的服务器上：905.258371ms

cat73 · cat73

终于通过了，真不容易。。。
之前的算法在我的电脑 150ms，现在只要 50ms。。。

然而效率仍然不是最高的。。。
分享下代码：

public class Solution {
// 为了递归拼接结果的时候少传俩参数才声明的全局变量
private final List<List<String>> results = new ArrayList<>();
private List<String> result;
/**
* 寻找最短的转换路径
*
* @param beginWord 开头单词
* @param endWord 结尾单词
* @param wordList 中间单词列表
* @return 最短路径列表
*/
public List<List<String>> findLadders(final String beginWord, final String endWord, final Set<String> wordList) {
// Main.expandTreeTiming.startTiming();
// 最大展开次数
final int maxLen = wordList.size() + 1;
// 移除与开头单词重复的中间单词
wordList.remove(beginWord);
// 将结尾单词添加到单词列表
wordList.add(endWord);
// 上一级节点列表
Map<String, TreeNode<String>> lastNodes = new HashMap<>(1);
// 将首个单词加入
lastNodes.put(beginWord, new TreeNode<>(beginWord));
// 按照中间单词数循环，如果在某个长度找到了可以转换的路径，则不再尝试下一个长度
int len = 1;
while (!lastNodes.containsKey(endWord) && len <= maxLen) {
// 当前级节点列表
final Map<String, TreeNode<String>> currentNodes = new HashMap<>(maxLen - lastNodes.size());
// 展开上一级树
for (final TreeNode<String> node : lastNodes.values()) {
final char[] chs = node.getValue().toCharArray();
// 遍历可以转换到的单词
for (int i = 0; i < chs.length; i++) {
String key;
final char bakCh = chs[i];
for (char ch = 'a'; ch <= 'z'; ch++) {
if (ch != bakCh) {
chs[i] = ch;
key = new String(chs);
// 找到一个单词
if (wordList.contains(key)) {
// 如果已经存在这个单词，则在其所属节点增加一个父节点，否则新建一个子节点
if (currentNodes.containsKey(key)) {
node.addChildNode(currentNodes.get(key));
} else {
final TreeNode<String> keyNode = new TreeNode<>(key);
node.addChildNode(keyNode);
currentNodes.put(key, keyNode);
}
}
}
}
chs[i] = bakCh;
}
}
// 用当前级节点列表覆盖上一级节点列表
lastNodes = currentNodes;
// 移除已使用过的中间单词
wordList.removeAll(currentNodes.keySet());
// 继续搜寻更长的路径
len += 1;
}
// Main.expandTreeTiming.stopTiming();
// Main.resultTiming.startTiming();
// 拼接结果
// 获取结尾单词所属的节点
final TreeNode<String> endNode = lastNodes.get(endWord);
// 如果存在该节点则开始递归拼接结果
if (endNode != null) {
// 准备临时保存结果的容器，并初始化所有元素为 null
this.result = new ArrayList<>(len);
for (int i = 0; i < len; i++) {
this.result.add(null);
}
// 调用递归拼接结果
this.addResults(endNode, len - 1);
}
// Main.resultTiming.stopTiming();
// 返回结果
return this.results;
}
/**
* 递归拼接结果
*
* @param node 当前节点
* @param index 当前节点的位置
*/
private void addResults(final TreeNode<String> node, final int index) {
this.result.set(index, node.getValue());
final List<TreeNode<String>> parentList = node.getParentNodes();
if (parentList.isEmpty()) {
this.results.add(new ArrayList<>(this.result));
} else {
for (final TreeNode<String> parentNode : parentList) {
this.addResults(parentNode, index - 1);
}
}
}
// =============
/**
* 多叉树节点
*
* @author cat73
*/
public class TreeNode<T> {
/**
* 当前节点的值
*/
private final T value;
/**
* 父节点列表
*/
private List<TreeNode<T>> parentNode;
/**
* 子节点列表
*/
private List<TreeNode<T>> childNodes;
/**
* 构造一个多叉树节点
*
* @param value 当前节点的值
*/
public TreeNode(final T value) {
this.value = value;
}
/**
* 获取当前节点的值
*
* @return 当前节点的值
*/
public T getValue() {
return this.value;
}
/**
* 获取父节点列表
*
* @return parentNode 当前节点所属的父节点列表
*/
public List<TreeNode<T>> getParentNodes() {
if (this.parentNode == null) {
this.parentNode = new ArrayList<>();
}
return this.parentNode;
}
/**
* 添加一个父节点
*
* @param childNode 要被添加的父节点
*/
private void addParentNode(final TreeNode<T> parentNode) {
if (this.parentNode == null) {
this.parentNode = new ArrayList<>();
}
this.parentNode.add(parentNode);
}
/**
* 获取子节点列表
*
* @return parentNode 当前节点所属的父节点列表
*/
public List<TreeNode<T>> getChildNodes() {
if (this.childNodes == null) {
this.childNodes = new ArrayList<>();
}
return this.childNodes;
}
/**
* 添加子节点(会同时在子节点增加父节点)
*
* @param childNode 要被添加的子节点
*/
public void addChildNode(final TreeNode<T> childNode) {
if (this.childNodes == null) {
this.childNodes = new ArrayList<>();
}
this.childNodes.add(childNode);
childNode.addParentNode(this);
}
}
}

复制代码

cat73 · cat73

顺便附送 Word Ladder 的答案（直接拿 II 的代码改的，可能效率不是很高了吧- -）

public class Solution {
/**
* 寻找最短的转换路径的长度
*
* @param beginWord 开头单词
* @param endWord 结尾单词
* @param wordList 中间单词列表
* @return 最短路径的长度
*/
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
// 最大展开次数
final int maxLen = wordList.size() + 1;
// 移除与开头单词重复的中间单词
wordList.remove(beginWord);
// 将结尾单词添加到单词列表
wordList.add(endWord);
// 上一级单词列表
Set<String> lastWords = new HashSet<>(1);
lastWords.add(beginWord);
// 按照中间单词数循环，如果在某个长度找到了可以转换的路径，则不再尝试下一个长度
int len = 1;
while (len <= maxLen) {
// 当前级节点列表
Set<String> currentWords = new HashSet<>(1);
// 寻找下一级单词列表
for (String word : lastWords) {
final char[] chs = word.toCharArray();
// 遍历可以转换到的单词
String key;
for (int i = 0; i < chs.length; i++) {
final char bakCh = chs[i];
for (char ch = 'a'; ch <= 'z'; ch++) {
if (ch != bakCh) {
chs[i] = ch;
key = new String(chs);
// 找到一个单词
if (wordList.contains(key)) {
wordList.remove(key);
if(key.equals(endWord)) {
// 返回结果
return len + 1;
} else {
currentWords.add(key);
}
}
}
}
chs[i] = bakCh;
}
}
// 用当前级单词列表覆盖上一级单词列表
lastWords = currentWords;
// 继续搜寻更长的路径
len += 1;
}
// 返回结果
return 0;
}
}

复制代码

zhaodecang · zhaodecang

哥们你玩的这些太高大上了，鄙人完全懵逼啊

帐号		自动登录	找回密码
密码			加入黑马

[学习交流] 发一道题目玩 0.0

10 个回复

点评