跳至主要內容
  • Hostloc 空間訪問刷分
  • 售賣場
  • 廣告位
  • 賣站?

4563博客

全新的繁體中文 WordPress 網站
  • 首頁
  • [leetcode/lintcode 题解] Google 面试题:单词矩阵
未分類
19 12 月 2020

[leetcode/lintcode 题解] Google 面试题:单词矩阵

[leetcode/lintcode 题解] Google 面试题:单词矩阵

資深大佬 : zzzrf 4

描述

给出一系列 ### 不重复的单词,找出所有用这些单词能构成的 单词矩阵。 一个有效的单词矩阵是指, 如果从第 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);         }     } } 

更多题解参考

大佬有話說 (0)

文章導覽

上一篇文章
下一篇文章

AD

其他操作

  • 登入
  • 訂閱網站內容的資訊提供
  • 訂閱留言的資訊提供
  • WordPress.org 台灣繁體中文

51la

4563博客

全新的繁體中文 WordPress 網站
返回頂端
本站採用 WordPress 建置 | 佈景主題採用 GretaThemes 所設計的 Memory
4563博客
  • Hostloc 空間訪問刷分
  • 售賣場
  • 廣告位
  • 賣站?
在這裡新增小工具