17.25. Word Rectangle
Description
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.
If there are more than one answer, return any one of them. A word can be used more than once.
Example 1:
Input: ["this", "real", "hard", "trh", "hea", "iar", "sld"] Output: [ "this", "real", "hard" ]
Example 2:
Input: ["aa"] Output: ["aa","aa"]
Notes:
words.length <= 1000
words[i].length <= 100
- It's guaranteed that all the words are randomly generated.
Solutions
Solution 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
|