[CareerCup] 18.13 Largest Rectangle of Letters - Grandyang - 博客园


[CareerCup] 18.13 Largest Rectangle of Letters - Grandyang - 博客园
18.13 Given a list of millions of words, design an algorithm to create the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom). The words need not be chosen consecutively from the list, but all rows must be the same length and all columns must be the same height.

private int maxWordLength;
private WordGroup[] groupList ;
private Trie trieList[];

public Question(String[] list) {
groupList = WordGroup.createWordGroups(list);
maxWordLength = groupList.length;
// Initialize trieList to store trie of groupList[i] at ith position.
trieList = new Trie[maxWordLength];
}

/* This function finds a rectangle of letters of the largest
* possible area (length x breadth) such that every row forms a
* word (reading left to right) from the list and every column
* forms a word (reading top to bottom) from the list.
*/
public Rectangle maxRectangle() {
// The dimensions of the largest possible rectangle.
int maxSize = maxWordLength * maxWordLength;

for (int z = maxSize; z > 0; z--) {
// Find out all pairs i,j less than maxWordLength
// such that i * j = z
for (int i = 1; i <= maxWordLength; i ++ ) {
if (z % i == 0) {
int j = z / i;
if (j <= maxWordLength) {
// Check if a Rectangle of length i and height
// j can be created.
Rectangle rectangle = makeRectangle(i,j);
if (rectangle != null) {
return rectangle;
}
}
}
}
}
return null;
}
/* This function takes the length and height of a rectangle as
* arguments. It tries to form a rectangle of the given length and
* height using words of the specified length as its rows, in which
* words whose length is the specified height form the columns. It
* returns the rectangle so formed, and null if such a rectangle
* cannot be formed.
*/
private Rectangle makeRectangle(int length, int height) {
if (groupList[length - 1] == null || groupList[height - 1] == null) {
return null;
}
if (trieList[height - 1] == null) {
ArrayList<String> words = groupList[height - 1].getWords();
trieList[height - 1] = new Trie(words);
}
return makePartialRectangle(length, height, new Rectangle(length));
}


/* This function recursively tries to form a rectangle with words
* of length l from the dictionary as rows and words of length h
* from the dictionary as columns. To do so, we start with an empty
* rectangle and add in a word with length l as the first row. We
* then check the trie of words of length h to see if each partial
* column is a prefix of a word with length h. If so we branch
* recursively and check the next word till we've formed a complete
* rectangle. When we have a complete rectangle check if every
* column is a word in the dictionary.
*/
private Rectangle makePartialRectangle(int l, int h, Rectangle rectangle) {

// Check if we have formed a complete rectangle by seeing if each column
// is in the dictionary
if (rectangle.height == h) {
if (rectangle.isComplete(l, h, groupList[h - 1])) {
return rectangle;
} else {
return null;
}
}

// If the rectangle is not empty, validate that each column is a
// substring of a word of length h in the dictionary using the
// trie of words of length h.
if (!rectangle.isPartialOK(l, trieList[h - 1])) {
return null;
}

// For each word of length l, try to make a new rectangle by adding
// the word to the existing rectangle.
for (int i = 0; i < groupList[l-1].length(); i++) {
Rectangle orgPlus = rectangle.append(groupList[l-1].getWord(i));
Rectangle rect = makePartialRectangle(l, h, orgPlus);
if (rect != null) {
return rect;
}
}
return null;
}
public class WordGroup {
private HashMap<String, Boolean> lookup = new HashMap<String, Boolean>();
   private ArrayList<String> group = new ArrayList<String>();  
   public boolean containsWord(String s) {
    return lookup.containsKey(s);
   }  
   public void addWord(String s) {
       group.add(s);
       lookup.put(s, true);
   }
 
   public int length() {
       return group.size();
   }
 
   public String getWord(int i) {
       return group.get(i);
   }
 
   public ArrayList<String> getWords(){
       return group;
   }
 
   public static WordGroup[] createWordGroups(String[] list) {
    WordGroup[] groupList;
    int maxWordLength = 0;
// Find out the length of the longest word
for (int i = 0; i < list.length; i++) {
if (list[i].length() > maxWordLength) {
maxWordLength = list[i].length();
}
}

/* Group the words in the dictionary into lists of words of
* same length.groupList[i] will contain a list of words, each
* of length (i+1). */
groupList = new WordGroup[maxWordLength];
for (int i = 0; i < list.length; i++) {
/* We do wordLength - 1 instead of just wordLength since this is used as
* an index and no words are of length 0 */
int wordLength = list[i].length() - 1;
if (groupList[wordLength] == null) {
groupList[wordLength] = new WordGroup();
}
groupList[wordLength].addWord(list[i]);
}
return groupList;
   }
}
public class Rectangle {
 
   // Rectangle data.
   public int height;
   public int length;
   public char [][] matrix;

   public Rectangle(int len) {
       this.length = len;
   }

   /* Construct a rectangular array of letters of the specified length
    * and height, and backed by the specified matrix of letters. (It is
    * assumed that the length and height specified as arguments are
    * consistent with the array argument's dimensions.)
    */
   public Rectangle(int length, int height, char[][] letters) {
       this.height = letters.length;
       this.length = letters[0].length;
       matrix = letters;
   }

   /* Return the letter present at the specified location in the array.
    */
   public char getLetter (int i, int j) {
       return matrix[i][j];
   }
 
   public String getColumn(int i) {
char[] column = new char[height];
for (int j = 0; j < height; j++) {
column[j] = getLetter(j, i);
}
return new String(column);
   }
 
   public boolean isComplete(int l, int h, WordGroup groupList) {
// Check if we have formed a complete rectangle.
if (height == h) {
// Check if each column is a word in the dictionary.
for (int i = 0; i < l; i++) {
String col = getColumn(i);
if (!groupList.containsWord(col)) {
return false; // Invalid rectangle.
}
}
return true; // Valid Rectangle!
}
return false;
   }
 
   public boolean isPartialOK(int l, Trie trie) {
    if (height == 0) {
    return true;
    }
for (int i = 0; i < l ; i++ ) {
String col = getColumn(i);
if (!trie.contains(col)) {
return false; // Invalid rectangle.
}
}
return true;
   }

   /* If the length of the argument s is consistent with that of this
    * Rectangle object, then return a Rectangle whose matrix is constructed by
    * appending s to the underlying matrix. Otherwise, return null. The
    * underlying matrix of this Rectangle object is /not/ modified.
    */
   public Rectangle append(String s) {
       if (s.length() == length) {
           char temp[][] = new char[height + 1][length];
           for (int i = 0; i < height; i++) {
               for (int j = 0; j < length; j++) {
                   temp[i][j] = matrix[i][j];
               }
           }
           s.getChars(0, length, temp[height], 0);

           return new Rectangle(length, height + 1, temp);
       }
       return null;
   }
}

https://github.com/wzhishen/cracking-the-coding-interview/blob/master/src/chap18/Q13.java
Read full article from [CareerCup] 18.13 Largest Rectangle of Letters - Grandyang - 博客园

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts