思路
dfs+剪枝。这里是枚举型dfs：模拟多层嵌套的for循环。因为单词长度最多为5，所以最多5层循环，但是这里还是使用dfs来实现，目的一个是为了美观，另外也是为了如果遇到很多层循环要嵌套的作准备。dfs的过程就是在一个一个尝试所有的可能性，如果两个单词能依次放在一起，那么二者就有一条边相连。这里说一下剪枝的过程：（1）在放下一个单词的时候，直接从之前放过的单词里计算一个前缀prefix出来，下一步只放带有该前缀的单词。其中使用hash来实现记录前缀的功能（也可以用字典树，更加节省空间）；（2）在第一步选择好之后，同时检查如果放了这个单词后，字典中是否含有进一步前缀的单词，没有的话也不能放第一步选出的单词。
代码
public class Solution {
public void initPrefix(String
[] words
, Map
<String
, List
<String>> hash
) {
for(String word
: words
) {
hash
.putIfAbsent("", new ArrayList<>());
hash
.get("").add(word
);
String prefix
= "";
for(int i
= 0; i
< word
.length(); i
++) {
prefix
+= word
.charAt(i
);
hash
.putIfAbsent(prefix
, new ArrayList<>());
hash
.get(prefix
).add(word
);
}
}
}
public boolean checkPrefix(int curPos
, int total
, String next
, Map
<String
, List
<String>> hash
, List
<String> path
) {
for(int i
= curPos
+ 1; i
< total
; i
++) {
String prefix
= "";
for(String word
: path
) {
prefix
+= word
.charAt(i
);
}
prefix
+= next
.charAt(i
);
if(!hash
.containsKey(prefix
)) {
return false;
}
}
return true;
}
public void dfs(int curPos
, int total
, Map
<String
, List
<String>> hash
, List
<List
<String>> res
, List
<String> path
) {
if(curPos
== total
) {
res
.add(new ArrayList<>(path
));
return;
}
String prefix
= "";
for(String word
: path
) {
prefix
+= word
.charAt(curPos
);
}
if(!hash
.containsKey(prefix
)) {
return;
}
for(String word
: hash
.get(prefix
)) {
if(!checkPrefix(curPos
, total
, word
, hash
, path
)) {
continue;
}
path
.add(word
);
dfs(curPos
+ 1, total
, hash
, res
, path
);
path
.remove(path
.size() - 1);
}
}
public List
<List
<String>> wordSquares(String
[] words
) {
Map
<String
, List
<String>> hash
= new HashMap<>();
List
<List
<String>> res
= new ArrayList<>();
List
<String> path
= new ArrayList<>();
if(words
== null
|| words
.length
== 0) {
return res
;
}
initPrefix(words
, hash
);
dfs(0, words
[0].length(), hash
, res
, path
);
return res
;
}
}
复杂度
时间复杂度
O
(
100
0
5
)
O(1000^5)
O(10005) 空间复杂度
O
(
n
2
)
O(n^2)
O(n2)
