m**q 发帖数: 189 | 1 Given a dictionary of millions of words, give an algorithm to find 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).
就是CareerCup150上的最后一题,不过它的答案我看的很糊涂。有人能帮忙解释下不?
多谢:) | b******4 发帖数: 1873 | 2 那个答案是这样做的
先把所有相同长度的words放在一个array中,然后你有N个array, N代表最长的words长度
可知最大的rectangle 的大小应该是所有长度为n的words组成的,既n x n大小
然后确定从哪两个bag拿words,假设bag A words length = x, bag B words length =
y
那么就开始从x * y最大且不超过 n x n这么大的情况开始
基本上是brute force的解决方法 | g**********y 发帖数: 14569 | |
|