求一道面世题的解答思路 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求一道面世题的解答思路

求一道面世题的解答思路# JobHunting - 待字闺中

b*f2011-07-22 07:07

1 楼

Word Rectangle
Write a program 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). Words should appear in this dictionary: WORD.LST (
1.66MB). Heuristic solutions that may not always produce a provably optimal
rectangle will be accepted: seek a reasonable tradeoff of efficiency and
optimality. (Hint: Use a B-Tree)
我只能想到把词典里的单词按长度分组，然后穷举法。感觉这样的话计算机要被搞死。
不知道哪位大虾有什么巧妙的方法！！

t*r2011-07-22 07:07

2 楼

好BT的题目啊

i*e2011-07-22 07:07

3 楼

这是 ITA 的 puzzle 题吧。
http://www.itasoftware.com/careers/work-at-ita/hiring-puzzles.h

that
word
(
optimal

【在 b*f 的大作中提到】

: Word Rectangle
: Write a program 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). Words should appear in this dictionary: WORD.LST (
: 1.66MB). Heuristic solutions that may not always produce a provably optimal
: rectangle will be accepted: seek a reasonable tradeoff of efficiency and
: optimality. (Hint: Use a B-Tree)
: 我只能想到把词典里的单词按长度分组，然后穷举法。感觉这样的话计算机要被搞死。
: 不知道哪位大虾有什么巧妙的方法！！

b*f2011-07-22 07:07

4 楼

考，还真是这里的一道题。
有人做过么？
求比穷举法好一点方法就行，
非常感谢！

【在 i**********e 的大作中提到】

: 这是 ITA 的 puzzle 题吧。
: http://www.itasoftware.com/careers/work-at-ita/hiring-puzzles.h
:
: that
: word
: (
: optimal

g*y2011-07-22 07:07

5 楼

Assumption: 你说的rectangle, 不是square, 那么比大小的话，只能比面积。
1. 把字典做成Trie
2. 预处理Matrix, 从上往下，从左往右，对位置(i, j), 如果水平向有长度k的单词，
把{i, j} 放进 SetY[k]; 如果纵向有长度k的单词，把{i, j} 放进 SetX[k].
3. 从大到小处理SetY[k], k最长好象是19，存在横向长度为k的word rectangle必要条
件：
- SetY[k]里包含(i, j), (i, j+1), ... (i, j+l)
For (t=l; t>0; t--) 扫描SetX[t], 看是否包含(I, j), (I+1, j), … (i+k, j). 如
果是，找到一word rectangle, 跟当前最大值比较，保存最大。然后退出循环。
SetY的元素，因为有序，处理一个后即可扔掉。
这个是地毯式搜索。

b*f2011-07-22 07:07

6 楼

谢谢你的算法。不过我没有看明白。
能不能帮忙解释下那个矩阵是什么，i,j是代表最后得到的矩形的横向和
纵向的字母位置吗？

【在 g**********y 的大作中提到】

: Assumption: 你说的rectangle, 不是square, 那么比大小的话，只能比面积。
: 1. 把字典做成Trie
: 2. 预处理Matrix, 从上往下，从左往右，对位置(i, j), 如果水平向有长度k的单词，
: 把{i, j} 放进 SetY[k]; 如果纵向有长度k的单词，把{i, j} 放进 SetX[k].
: 3. 从大到小处理SetY[k], k最长好象是19，存在横向长度为k的word rectangle必要条
: 件：
: - SetY[k]里包含(i, j), (i, j+1), ... (i, j+l)
: For (t=l; t>0; t--) 扫描SetX[t], 看是否包含(I, j), (I+1, j), … (i+k, j). 如
: 果是，找到一word rectangle, 跟当前最大值比较，保存最大。然后退出循环。
: SetY的元素，因为有序，处理一个后即可扔掉。

g*y2011-07-22 07:07

7 楼

i是横坐标，j是纵坐标。最后的位置另外用变量来记录。

【在 b*f 的大作中提到】

: 谢谢你的算法。不过我没有看明白。
: 能不能帮忙解释下那个矩阵是什么，i,j是代表最后得到的矩形的横向和
: 纵向的字母位置吗？

i*e2011-07-22 07:07

8 楼

Did you try trie?
If you just find the largest square, then the problem become much easier and
more optimization can be done.
My program found a 7x7 solution within 10 seconds, and there are a lot of
7x7 solutions. Finding all of them would take a long time though.
I think there is a 8x8 solution as well, if you wait long enough.

g*y2011-07-22 07:07

9 楼

I think I misunderstand the original problem. Now I re-read it after seeing
your answer. It looks like:
Using given dictionary, form a matrix as large as possible, satisfying the
conditions.
My previous read was: given dictionary and a large matrix, find largest
square in it, satisfying conditions.
It's an interesting challenge. I will try it.

and

【在 i**********e 的大作中提到】

: Did you try trie?
: If you just find the largest square, then the problem become much easier and
: more optimization can be done.
: My program found a 7x7 solution within 10 seconds, and there are a lot of
: 7x7 solutions. Finding all of them would take a long time though.
: I think there is a 8x8 solution as well, if you wait long enough.

i*e2011-07-22 07:07

10 楼

I've run my code for 3-4 hours now, and I've got 5 answers for 8x8 so far.
The program should finish within a day searching all 8x8 solutions.

i*e2011-07-22 07:07

11 楼

Hehe, seemed like there's only five 8x8 solutions.
Very likely that there's no solution for 9x9 and above.

b*f2011-07-22 07:07

12 楼

Yes, it is to find the largest rectangular, not square.
But I still don't understand the matrix you mentioned.
What is the element of the matrix, such as cell(i,j)?
Do you mean a word or a letter?
Thanks again!

seeing

【在 g**********y 的大作中提到】

: I think I misunderstand the original problem. Now I re-read it after seeing
: your answer. It looks like:
: Using given dictionary, form a matrix as large as possible, satisfying the
: conditions.
: My previous read was: given dictionary and a large matrix, find largest
: square in it, satisfying conditions.
: It's an interesting challenge. I will try it.
:
: and

g*y2011-07-22 07:07

13 楼

cell(i,j) is a letter.
Use ihasleetcode's idea, do a DFS search of words form a matrix, when you
form such matrix, use trie as cut condition.
This is a CPU intensive problem. Depends on how to design the cut, and how
effective it is, program can run days to search all solutions.
I am trying different ways. If find some effective way, I will post code
here.

【在 b*f 的大作中提到】

: Yes, it is to find the largest rectangular, not square.
: But I still don't understand the matrix you mentioned.
: What is the element of the matrix, such as cell(i,j)?
: Do you mean a word or a letter?
: Thanks again!
:
: seeing

g*y2011-07-22 07:07

14 楼

ihasleetcode能谈一下你的思路吗？我算了一下，普通的剪枝效率很不够。
长度7的单词，那个list里有23208个。
第一行，所有词都可能。
第一列，被第一行限制后，还是有~1000个词满足前缀。
第二行，被第一列限制后，也有~1000个词满足前缀。
第二列，被前两行限制后，可能有~50个词满足前缀。
从那以后，trie的剪枝才开始真正工作。
这个数量级已经是差不多10^12, 我很难想象这种办法基础上的检索能10秒出结果。
还是你算法完全不一样？

and

【在 i**********e 的大作中提到】

i*e2011-07-22 07:07

15 楼

我们的思路基本应该是一样的。
就是一行一行进行搜索，每一列一个 trie，当前的行也有一个 trie.
每要填一个空格时，必定要满足行和列的要求。如果满足的话，进行下一列搜索。
一开始每个 trie 节点有 26 个 children，以数组来表示。
我发现用链表来表示 children 可以增快速度至少 20%.

【在 g**********y 的大作中提到】

: ihasleetcode能谈一下你的思路吗？我算了一下，普通的剪枝效率很不够。
: 长度7的单词，那个list里有23208个。
: 第一行，所有词都可能。
: 第一列，被第一行限制后，还是有~1000个词满足前缀。
: 第二行，被第一列限制后，也有~1000个词满足前缀。
: 第二列，被前两行限制后，可能有~50个词满足前缀。
: 从那以后，trie的剪枝才开始真正工作。
: 这个数量级已经是差不多10^12, 我很难想象这种办法基础上的检索能10秒出结果。
: 还是你算法完全不一样？
:

g*y2011-07-22 07:07

16 楼

我的计算有点不同：计算行时我没直接用trie, 而是遍历所有可能的词(第一列我是先
填上的), 然后对词的每个字母用trie来计算是否满足列的标准，这组trie是逐行pass
到下一行的。
除此之外，可能是程序还有地方效率不好，我计算长度7的矩阵，15分钟都还没出结果。

【在 i**********e 的大作中提到】

: 我们的思路基本应该是一样的。
: 就是一行一行进行搜索，每一列一个 trie，当前的行也有一个 trie.
: 每要填一个空格时，必定要满足行和列的要求。如果满足的话，进行下一列搜索。
: 一开始每个 trie 节点有 26 个 children，以数组来表示。
: 我发现用链表来表示 children 可以增快速度至少 20%.

i*e2011-07-22 07:07

17 楼

那为什么行的时候不用 trie 来验证是否满足要求？
如果不满足就不必进行下一列的搜索了。等到所有列都填满了才验证行是否也满足要求
，那搜索组合相对来说也会比较多。

pass
果。

【在 g**********y 的大作中提到】

: 我的计算有点不同：计算行时我没直接用trie, 而是遍历所有可能的词(第一列我是先
: 填上的), 然后对词的每个字母用trie来计算是否满足列的标准，这组trie是逐行pass
: 到下一行的。
: 除此之外，可能是程序还有地方效率不好，我计算长度7的矩阵，15分钟都还没出结果。

b*f2011-07-22 07:07

18 楼

加油加油，
用一个小辞典先帮我搞出一个可行的代码可以不？
我急着用：）

【在 g**********y 的大作中提到】

i*e2011-07-22 07:07

19 楼

你急着干嘛？

【在 b*f 的大作中提到】

: 加油加油，
: 用一个小辞典先帮我搞出一个可行的代码可以不？
: 我急着用：）

g*y2011-07-22 07:07

20 楼

代码不难，ihasleetcode都解释得很清楚，你自己也能写吧。

【在 b*f 的大作中提到】

: 加油加油，
: 用一个小辞典先帮我搞出一个可行的代码可以不？
: 我急着用：）

b*f2011-07-22 07:07

21 楼

不好意思，我是要发个代码过去，才能捞个面试机会。
可能我脑子太水，看了你们的所有帖子，还是没搞懂
应该怎么做。
据我对题的理解，应该不是正方形，而是最大面积的
长方形。假设最终结果是长N高M,那就是要M个N字母的
单词横着排列,还要满足竖着的N列刚好都是M字母的单词，
而这些单词都在词典中。
你们的思路是不是先假定知道N和M, 然后从字典中N子母单词
组和M字母单词组挑单词来排列组合，看是否满足要求？
感觉这个工作量也太大了？只能穷举无数种情况，即使对
一个 MxN 已知大小的矩阵.

【在 g**********y 的大作中提到】

: 代码不难，ihasleetcode都解释得很清楚，你自己也能写吧。

g*y2011-07-22 07:07

22 楼

如果你的算法足够快，穷举也是可行的。
可以假定N >= M，因为N < M的情况，对称也能找出来。
从字典可以知道 1<=N<=28, 所以你地毯式地搜也行。
但是从知道的情况看，ihasleetcode的code运行到N=8时，时间就很长了。我写的code
速度更慢。
现实地说，你要凭这个题拿面试，需要更有效的剪枝，或者是启发式算法，或者近似算
法。

【在 b*f 的大作中提到】

: 不好意思，我是要发个代码过去，才能捞个面试机会。
: 可能我脑子太水，看了你们的所有帖子，还是没搞懂
: 应该怎么做。
: 据我对题的理解，应该不是正方形，而是最大面积的
: 长方形。假设最终结果是长N高M,那就是要M个N字母的
: 单词横着排列,还要满足竖着的N列刚好都是M字母的单词，
: 而这些单词都在词典中。
: 你们的思路是不是先假定知道N和M, 然后从字典中N子母单词
: 组和M字母单词组挑单词来排列组合，看是否满足要求？
: 感觉这个工作量也太大了？只能穷举无数种情况，即使对

g*y2011-07-22 07:07

23 楼

我写的慢程序：用HashMap实现的Trie. 换成char[], 对于N=7, 速度快一些，但是对N<
7, 速度更慢。可能因为解跟Hash key的位置有关。
public class WordRectangle {
private final static String DIR = "src/test/resources";

private Trie m_trie;
private String[] m_words;
public static void main(String[] args) {
WordRectangle w = new WordRectangle();
long t0 = System.currentTimeMillis();
w.find(6);
long t1 = System.currentTimeMillis();
System.out.println("Time = " + (t1-t0));
}
public void find(int N) {
m_trie = new Trie();
m_words = readWords(N);

for (String word : m_words) {
m_trie.addWord(word);
}

char[][] solution = new char[N][N];
Trie[][] trie = new Trie[N][N];
for (String word : m_words) {
solution[0] = word.toCharArray();
for (int i=0; ii]);

if (search(solution, trie, m_trie, 1, 0, N)) {
print(solution, N);
return;
}
}
}

private void print(char[][] solution, int N) {
for (int i=0; ifor (int j=0; jSystem.out.println();
}
}

private boolean search(char[][] solution, Trie[][] trie, Trie row, int i
, int j, int N) {
if (i == N) return true;
if (j == N) return search(solution, trie, m_trie, i+1, 0, N);
for (char c : trie[i-1][j].keySet()) {
Trie hNext = row.getNode(c);
if (hNext != null) {
solution[i][j] = c;
trie[i][j] = trie[i-1][j].getNode(c);
if (search(solution, trie, hNext, i, j+1, N)) return true;
}
}
return false;
}

private String[] readWords(int N) {
String content = FileHelper.readFile(DIR + "/WORD" + N + ".LST");
return content.split("\n");
}
}
public class Trie {
private HashMap children;

public Trie() {
children = new HashMap();
}

public void addWord(String word) {
char[] c = word.toCharArray();
Trie parent = this;
for (int i=0; iif (!parent.children.containsKey(c[i])) {
parent.children.put(c[i], new Trie());
}
parent = parent.getNode(c[i]);
}
}

public Trie getNode(char c) {
return children.get(c);
}

public Set keySet() {
return children.keySet();
}
}

b*f2011-07-22 07:07

24 楼

多谢大侠，
我先研究研究，看能不能看懂你的算法。

N<

【在 g**********y 的大作中提到】

: 我写的慢程序：用HashMap实现的Trie. 换成char[], 对于N=7, 速度快一些，但是对N<
: 7, 速度更慢。可能因为解跟Hash key的位置有关。
: public class WordRectangle {
: private final static String DIR = "src/test/resources";
:
: private Trie m_trie;
: private String[] m_words;
: public static void main(String[] args) {
: WordRectangle w = new WordRectangle();
: long t0 = System.currentTimeMillis();

g*y2011-07-22 07:07

25 楼

看答案发现，对于NxN的矩阵，如果有解，多半都有对称解。全搜索所有空间慢，但是
搜对称空间还是很容易的。这是搜对称空间的投机取巧结果(时间ms), N>8时，无解：
N = 2
a a
a a
Time = 15
N = 3
a a h
a b a
h a d
Time = 0
N = 4
a a h s
a b e t
h e b e
s t e m
Time = 16
N = 5
a a h e d
a b a c i
h a o l e
e c l a t
d i e t s
Time = 16
N = 6
a a h i n g
a g o n a l
h o o d i e
i n d o l e
n a i l e d
g l e e d s
Time = 15
N = 7
a b a s e r s
b e d e m e n
a d e n o m a
s e n a t o r
e m o t i v e
r e m o v e r
s n a r e r s
Time = 94
N = 8
c a r b o r a s
a p e r i e n t
r e c a l l e r
b r a s s i c a
o i l s e e d s
r e l i e v o s
a n e c d o t e
s t r a s s e s
Time = 11891

g*y2011-07-22 07:07

26 楼

N=7时，有3559组对称解
N=8时，有3组对称解

i*e2011-07-22 07:07

27 楼

N=8 有5组解，而且全是对称的。
Total words with len = 8: 28558
Starting DFS...
carboras
aperient
recaller
brassica
oilseeds
relievos
anecdote
strasses
crabwise
ratlines
atlantes
blastema
winterly
intertie
seemlier
essayers
nereides
energise
resonate
erotized
igniters
diazepam
esterase
seedsmen
nereides
eternise
relocate
erotized
inciters
diazepam
esterase
seedsmen
nereides
eternise
renovate
erotized
inviters
diazepam
esterase
seedsmen
没错，对称解可以很快搜索出来，但是只适用于正方形。
N>=9 没有对称解，所以很大可能性没有解。

【在 g**********y 的大作中提到】

: N=7时，有3559组对称解
: N=8时，有3组对称解

g*y2011-07-22 07:07

28 楼

Got it. 对第一行，我填了一个词后，只找了一组解。所以就漏过了最后2组。
BTW，能不能贴一下你的code? 我改了之后，全搜索的话还是要30s才算出7的第一组解
。我想可能还有什么没考虑到的误区。

【在 i**********e 的大作中提到】

: N=8 有5组解，而且全是对称的。
: Total words with len = 8: 28558
: Starting DFS...
: carboras
: aperient
: recaller
: brassica
: oilseeds
: relievos
: anecdote

b*f2011-07-22 07:07

29 楼

请问你的代码能搜索矩阵的情况吗？
比如给定N=7, M=5

【在 g**********y 的大作中提到】

: 看答案发现，对于NxN的矩阵，如果有解，多半都有对称解。全搜索所有空间慢，但是
: 搜对称空间还是很容易的。这是搜对称空间的投机取巧结果(时间ms), N>8时，无解：
: N = 2
: a a
: a a
: Time = 15
: N = 3
: a a h
: a b a
: h a d

g*y2011-07-22 07:07

30 楼

对称的，你说能吗？:)

【在 b*f 的大作中提到】

: 请问你的代码能搜索矩阵的情况吗？
: 比如给定N=7, M=5

g*y2011-07-22 07:07

31 楼

终于发现问题所在了：
在search()里，我把trie[i-1][j].getNode() call了两遍，而且有很多无用的getNode
() call. (search a-z)
现在把Trie的keyset preprocess，N=7时，10秒以内可以出结果了。
顺便说一下，刚发现这个新工具: JDK自带的jvisualvm, 做profiler很好用，简单到极致。Eclipse的那个TPTP, 复杂到没用。

b*f2011-07-22 07:07

32 楼

但原题的要求是任意矩形阿。
是不是那样的难度要高一个数量级？

【在 g**********y 的大作中提到】

: 对称的，你说能吗？:)

i*e2011-07-22 07:07

33 楼

很明显阿。。。
你看问题里提到：“Heuristic solutions that may not always produce a provably
optimal rectangle will be accepted: seek a reasonable tradeoff of
efficiency and optimality.”
如果你要寻找最大的任意矩形而这答案必须正确，是不可能在短时间内搜索到的。

【在 b*f 的大作中提到】

: 但原题的要求是任意矩形阿。
: 是不是那样的难度要高一个数量级？

i*e2011-07-22 07:07

34 楼

你指的是只搜索对称的，还是搜索包括所有的 solution space（包括不对称的）？
如果是对称的，十秒钟就可以搜完所有答案。如果是所有的 solution space，7x7 的
需要 7 秒钟得到第一个答案。搜索完所有 7x7 的答案我就不知道了，应该差不多要半
天时间吧。

【在 g**********y 的大作中提到】

: Got it. 对第一行，我填了一个词后，只找了一组解。所以就漏过了最后2组。
: BTW，能不能贴一下你的code? 我改了之后，全搜索的话还是要30s才算出7的第一组解
: 。我想可能还有什么没考虑到的误区。

g*y2011-07-22 07:07

35 楼

搜所有空间的，7x7，我搜第一个答案用10s。

【在 i**********e 的大作中提到】

: 你指的是只搜索对称的，还是搜索包括所有的 solution space（包括不对称的）？
: 如果是对称的，十秒钟就可以搜完所有答案。如果是所有的 solution space，7x7 的
: 需要 7 秒钟得到第一个答案。搜索完所有 7x7 的答案我就不知道了，应该差不多要半
: 天时间吧。

g*y2011-07-22 07:07

36 楼

对NxN, 想到一种加速的办法：
全空间搜索时，其实有很多重复的搜索，这是对称性决定的。比如第一行单词为alaska
, 那么第一列就不用搜任何字典序大于alaska的单词 -- 因为这种组合后面会被搜到。
这样加速后，7x7用0.2秒就可以出来。8x8还是很长，算了几分钟，还没出结果。

i*e2011-07-22 07:07

37 楼

这可不一定。
反例，这里有个 5x5 的 word square 就不是对称解。第一行是 'aahed'，而第一列则
是 'ached'.
aahed
clone
hoist
ensue
deter
当 N 越大，存在不对称的解可能性就大大减少。但这却不能排除掉存在的可能性。

alaska

【在 g**********y 的大作中提到】

: 对NxN, 想到一种加速的办法：
: 全空间搜索时，其实有很多重复的搜索，这是对称性决定的。比如第一行单词为alaska
: , 那么第一列就不用搜任何字典序大于alaska的单词 -- 因为这种组合后面会被搜到。
: 这样加速后，7x7用0.2秒就可以出来。8x8还是很长，算了几分钟，还没出结果。

i*e2011-07-22 07:07

38 楼

我用 C++ 优化到最快可以 5.6 秒，搜索所有空间 7x7 得到第一个解。

【在 g**********y 的大作中提到】

: 搜所有空间的，7x7，我搜第一个答案用10s。

g*y2011-07-22 07:07

39 楼

我的意思是，aahed第一行，就不用搜ached第一列，因为
ached
alone
hoist
ensue
deter
是解，不会被漏过。

【在 i**********e 的大作中提到】

: 这可不一定。
: 反例，这里有个 5x5 的 word square 就不是对称解。第一行是 'aahed'，而第一列则
: 是 'ached'.
: aahed
: clone
: hoist
: ensue
: deter
: 当 N 越大，存在不对称的解可能性就大大减少。但这却不能排除掉存在的可能性。
: