LintCode 634 Word Squares (LeetCode 425)

思路

dfs+剪枝。这里是枚举型dfs：模拟多层嵌套的for循环。因为单词长度最多为5，所以最多5层循环，但是这里还是使用dfs来实现，目的一个是为了美观，另外也是为了如果遇到很多层循环要嵌套的作准备。dfs的过程就是在一个一个尝试所有的可能性，如果两个单词能依次放在一起，那么二者就有一条边相连。这里说一下剪枝的过程：（1）在放下一个单词的时候，直接从之前放过的单词里计算一个前缀prefix出来，下一步只放带有该前缀的单词。其中使用hash来实现记录前缀的功能（也可以用字典树，更加节省空间）；（2）在第一步选择好之后，同时检查如果放了这个单词后，字典中是否含有进一步前缀的单词，没有的话也不能放第一步选出的单词。

代码

public class Solution {
    /** @param words: a set of words without duplicates* @return: all word squares*/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) {
    // write your code hereMap<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(1000^5)$
空间复杂度$O(n^2)$