[leetcode/lintcode 题解] Google 面试题:单词矩阵
描述
给出一系列 ### 不重复的单词,找出所有用这些单词能构成的 单词矩阵。 一个有效的单词矩阵是指, 如果从第 k 行读出来的单词和第 k 列读出来的单词相同(0 <= k < max(numRows, numColumns)),那么就是一个单词矩阵. 例如,单词序列为 [“ball”,”area”,”lead”,”lady”] ,构成一个单词矩阵。因为对于每一行和每一列,读出来的单词都是相同的。
b a l l a r e a l e a d l a d y
在线评测地址
现在至少有一个单词并且不多于 1000 个单词 所有的单词都有相同的长度 单词的长度最短为 1 最长为 5 每一个单词均由小写字母组成
样例 1:
输入: ["area","lead","wall","lady","ball"] 输出: [["wall","area","lead","lady"],["ball","area","lead","lady"]] 解释: 输出包含 两个单词矩阵,这两个矩阵的输出的顺序没有影响(只要求矩阵内部有序)。
样例 2:
输入: ["abat","baba","atan","atal"] 输出: [["baba","abat","baba","atan"],["baba","abat","baba","atal"]]
算法:DFS+hashmap
枚举 dfs, 如果两个单词能依次放在一起,那么二者就有一条边相连。可分两种情况剪枝:1.在放下一个单词的时候,直接从之前放过的单词里计算一个前缀 prefix 出来,下一步只放带有该前缀的单词。其中使用 hashmap 来实现记录前缀的功能。2.在第一步选择好之后,同时检查如果放了这个单词后,字典中是否含有进一步前缀的单词,没有的话也不能放第一步选出的单词
根据样例举例:words = [“area”,“lead”,“wall”,“lady”,“ball”]
我们先让 prefix[“”]=words, 然后将所有字符串的的前缀和对应字符串都放到 prefix 这个 hash table 里面
squares[][]这个里面是放已经找好的 words,当已经找到了 wordLen 个字符串之后就是一个可行解了,放到 results 里面
checkPrefix(index, nextWord)这个函数是在第 index+1 到 wordLen 的列中,找第 0 到 index – 1 行中找到 pre 前缀
比如 squares = [wall, area, lead],index = 3,此时 pre 遍历 squares,把每个字符串的第 3 个字符拼起来,即 lad,然后再与还不在 squares 中的字符串(lady, ball)的第 3 个字符挨个拼起来,看是不是在 prefix 里面。这里先处理 lady, lad+y=lady,在 prefix 里面,所以 squares=[wall, area, lead, lady]是一个可行解,放入 results 。
复杂度分析
时间复杂度 O(1000^5) 经过剪枝,预计复杂度 26^2 空间复杂度 O(n^2) 存储 hash 等关系
public class Solution { /* * @param words: a set of words without duplicates * @return: all word squares */ private int wordlen = 0; private Map<String,List<String>> prefix = new HashMap<String,List<String>>(); private List<String> squares = new ArrayList<String>(); private List<List<String>> res = new ArrayList<List<String>>(); public List<List<String>> wordSquares(String[] words) { if (words == null || words.length == 0) { return res; } initprefixes(words); wordlen = words[0].length(); dfs(0); return res; } //预处理得到 prefix private void initprefixes(String[] words) { for(String word : words) { prefix.putIfAbsent("", new ArrayList<>()); prefix.get("").add(word); String pre = ""; for (int i = 0; i < word.length(); i++) { pre += word.charAt(i); prefix.putIfAbsent(pre, new ArrayList<>()); prefix.get(pre).add(word); } } } private boolean checkPrefix(int index,String next) { for(int i = index + 1; i < wordlen; i++) { String pre = ""; for (int j = 0; j < index; ++j) { pre += squares.get(j).charAt(i); } pre += next.charAt(i); if(!prefix.containsKey(pre)) { return false; } } return true; } private void dfs(int index) { if (index == wordlen) { res.add(new ArrayList<>(squares)); return ; } String pre = ""; for (int i = 0;i < index;i++) { pre += squares.get(i).charAt(index); } List<String> matchedWords = new ArrayList<String>(prefix.get(pre)); int m = matchedWords.size(); for (int i = 0;i < m;i++) { //找到 pre 前缀 if (!checkPrefix(index, matchedWords.get(i))) { continue; } squares.add(matchedWords.get(i)); dfs(index + 1); squares.remove(squares.size() - 1); } } }
更多题解参考