《Cracking the Coding Interview》――第18章：难题――题目13 - zhuli19901106 - 博客园

《Cracking the Coding Interview》――第18章：难题――题目13 - zhuli19901106 - 博客园

题目：给定一个字母组成的矩阵，和一个包含一堆单词的词典。请从矩阵中找出一个最大的子矩阵，使得从左到右每一行，从上到下每一列组成的单词都包含在词典中。

解法：O(n^3)级别的时间和空间进行动态规划。这道题目和第17章的最后一题很像，由于这题的时间复杂度实在是高，我动手写了字典树进行加速。如果单纯用哈希表来作为词典，查询效率实际会达到O(n)级别，导致最终的算法复杂度为O(n^4)。用字典树则可以加速到O(n^3)，因为对于一个字符串"abcd"，只需要从字典树的根节点出发往下走，就可以一次性判断"a"、"ab"、"abc"、"abcd"是否包含在字典里，而用哈希表无法做到这样的效率。动态规划过程仍然是O(n^4)级别，字典树只是将查单词的过程中进行了加速，从O(n^4)加速到了O(n^3)。空间复杂度为O(n^3)，用于标记横向和纵向的每一个子段是否包含在字典里。

Read full article from 《Cracking the Coding Interview》――第18章：难题――题目13 - zhuli19901106 - 博客园