好想拿，可是手里已经满了呢~ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Joke - 肚皮舞运动

好想拿，可是手里已经满了呢~

好想拿，可是手里已经满了呢~# Joke - 肚皮舞运动

c*m2015-01-06 08:01

1 楼

看两个A家面经里面有这题:
给你一个board, 一个dict让你计算最多能有多少个valid单词出现在这个Board上面。
限制是board中的一个字母只能被一个单词使用，比如走了一个词apple, 那么a, p, p,
l, e这几个char的位置不能再被其它单词用了。
补充：看题意一个单词应该是由board中连续的字母组成的。除了brute force想不到啥
好方法，大牛们能指点下么？

f*e2015-01-06 08:01

2 楼

a*12015-01-06 08:01

3 楼

leetcode 原题吧，word search I/II

p*e2015-01-06 08:01

4 楼

有点像赵本山

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

c*m2015-01-06 08:01

5 楼

修改了题目。board中一个字母只能被一个选中的word所使用。

【在 a******1 的大作中提到】

: leetcode 原题吧，word search I/II

l*t2015-01-06 08:01

6 楼

周立波

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

: 有点像赵本山

h*c2015-01-06 08:01

7 楼

先找到所有的合法字符串，然后按容斥性画一个图，最后找最大完全图(这个是NP hard
)。

p,

【在 c*****m 的大作中提到】

: 看两个A家面经里面有这题:
: 给你一个board, 一个dict让你计算最多能有多少个valid单词出现在这个Board上面。
: 限制是board中的一个字母只能被一个单词使用，比如走了一个词apple, 那么a, p, p,
: l, e这几个char的位置不能再被其它单词用了。
: 补充：看题意一个单词应该是由board中连续的字母组成的。除了brute force想不到啥
: 好方法，大牛们能指点下么？

s*r2015-01-06 08:01

8 楼

re

【在 l****t 的大作中提到】

: 周立波

r*g2015-01-06 08:01

9 楼

不懂
如果一个字母同时属于两个单词，在图上面是什么关系？
谢谢了。

hard

【在 h*c 的大作中提到】

: 先找到所有的合法字符串，然后按容斥性画一个图，最后找最大完全图(这个是NP hard
: )。
:
: p,

s*e2015-01-06 08:01

10 楼

Gollum的神情

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

c*m2015-01-06 08:01

11 楼

本版的大牛们已经完全不讨论题了么？看来得转去一亩三分地了

c*m2015-01-06 08:01

12 楼

本版的大牛们已经完全不讨论题了么？看来得转去一亩三分地了

y*a2015-01-06 08:01

13 楼

I think hoc has answered your question.

【在 c*****m 的大作中提到】

: 本版的大牛们已经完全不讨论题了么？看来得转去一亩三分地了

I*c2015-01-06 08:01

14 楼

leecode上的word search I/II说白了就是backtracking/穷举嘛。这道题也可以用嘛
把每个词在board上的位置记下来（如果这个词存在于board上的话）。然后就
backtracking每个词。如果一个词在board上有多个的可能，那试的时候就把多个可能
都试一下。

r*g2015-01-06 08:01

15 楼

大侠，还是不懂啊，求指点，和图有何关系
谢谢了

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

:
: I think hoc has answered your question.

n*n2015-01-06 08:01

16 楼

这题就是leetcode word search 2在输出结果的时候mark下trie的第一级子节点，最后
count个数。

p,

【在 c*****m 的大作中提到】

l*82015-01-06 08:01

17 楼

也就直接dfs吧。

p,

【在 c*****m 的大作中提到】

f*s2015-01-06 08:01

18 楼

这个算Brutal force吗？

★ 发自iPhone App: ChineseWeb 1.0.6

【在 I******c 的大作中提到】

: leecode上的word search I/II说白了就是backtracking/穷举嘛。这道题也可以用嘛
: 把每个词在board上的位置记下来（如果这个词存在于board上的话）。然后就
: backtracking每个词。如果一个词在board上有多个的可能，那试的时候就把多个可能
: 都试一下。