word-rectangle-lcci

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。

英文版：Cracking the Coding Interview，源自硅谷程序员的面试红宝书

LCCI

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:

<pre>
Input: <code>[&quot;this&quot;, &quot;real&quot;, &quot;hard&quot;, &quot;trh&quot;, &quot;hea&quot;, &quot;iar&quot;, &quot;sld&quot;]</code>
Output:
<code>[
&nbsp; &quot;this&quot;,
&nbsp; &quot;real&quot;,
&nbsp; &quot;hard&quot;</code>
]</pre>

Example 2:

<pre>
Input: <code>[&quot;aa&quot;]</code>
Output: [&quot;aa&quot;,&quot;aa&quot;]</pre>

Notes: 

<ul>
	<li><code>words.length &lt;= 1000</code></li>
	<li><code>words[i].length &lt;= 100</code></li>
	<li>It&#39;s guaranteed that&nbsp;all the words are randomly generated.</li>
</ul>

maxRectangle

Word Rectangle LCCI

Trie

Array

String

Backtracking

给定一份单词的清单，设计一个算法，创建由字母组成的面积最大的矩形，其中每一行组成一个单词(自左向右)，每一列也组成一个单词(自上而下)。不要求这些单词在清单里连续出现，但要求所有行等长，所有列等高。

如果有多个面积最大的矩形，输出任意一个均可。一个单词可以重复使用。

示例 1：

<pre>
输入：<code>["this", "real", "hard", "trh", "hea", "iar", "sld"]</code>
输出：
<code>[
&nbsp; "this",
&nbsp; "real",
&nbsp; "hard"</code>
]</pre>

示例 2：

<pre>
输入：<code>["aa"]</code>
输出：["aa","aa"]</pre>

说明：

<ul>
	<li><code>words.length &lt;= 1000</code></li>
	<li><code>words[i].length &lt;= 100</code></li>
	<li>数据保证单词足够随机</li>
</ul>