c*****m
发帖数: 271 | 1 看两个A家面经里面有这题:
给你一个board, 一个dict让你计算最多能有多少个valid单词出现在这个Board上面。
限制是board中的一个字母只能被一个单词使用，比如走了一个词apple, 那么a, p, p,
l, e这几个char的位置不能再被其它单词用了。
补充：看题意一个单词应该是由board中连续的字母组成的。除了brute force想不到啥
好方法，大牛们能指点下么？ |
a******1
发帖数: 20 | 2 leetcode 原题吧，word search I/II |
c*****m
发帖数: 271 | 3 修改了题目。board中一个字母只能被一个选中的word所使用。
【在 a******1 的大作中提到】
: leetcode 原题吧，word search I/II
|
h*c
发帖数: 45 | 4 先找到所有的合法字符串，然后按容斥性画一个图，最后找最大完全图(这个是NP hard
)。
p,
【在 c*****m 的大作中提到】
: 看两个A家面经里面有这题:
: 给你一个board, 一个dict让你计算最多能有多少个valid单词出现在这个Board上面。
: 限制是board中的一个字母只能被一个单词使用，比如走了一个词apple, 那么a, p, p,
: l, e这几个char的位置不能再被其它单词用了。
: 补充：看题意一个单词应该是由board中连续的字母组成的。除了brute force想不到啥
: 好方法，大牛们能指点下么？
|
r*******g
发帖数: 1335 | 5 不懂
如果一个字母同时属于两个单词，在图上面是什么关系？
谢谢了。
hard
【在 h*c 的大作中提到】
: 先找到所有的合法字符串，然后按容斥性画一个图，最后找最大完全图(这个是NP hard
: )。
:
: p,
|
c*****m
发帖数: 271 | 6 本版的大牛们已经完全不讨论题了么？看来得转去一亩三分地了 |
c*****m
发帖数: 271 | 7 本版的大牛们已经完全不讨论题了么？看来得转去一亩三分地了 |
y**********a
发帖数: 824 | 8
I think hoc has answered your question.
【在 c*****m 的大作中提到】
: 本版的大牛们已经完全不讨论题了么？看来得转去一亩三分地了
|
I******c
发帖数: 163 | 9 leecode上的word search I/II说白了就是backtracking/穷举嘛。这道题也可以用嘛
把每个词在board上的位置记下来（如果这个词存在于board上的话）。然后就
backtracking每个词。如果一个词在board上有多个的可能，那试的时候就把多个可能
都试一下。 |
r*******g
发帖数: 1335 | 10 大侠，还是不懂啊，求指点，和图有何关系
谢谢了
【在 y**********a 的大作中提到】
:
: I think hoc has answered your question.
|
n*******n
发帖数: 202 | 11 这题就是leetcode word search 2在输出结果的时候mark下trie的第一级子节点，最后
count个数。
p,
【在 c*****m 的大作中提到】
: 看两个A家面经里面有这题:
: 给你一个board, 一个dict让你计算最多能有多少个valid单词出现在这个Board上面。
: 限制是board中的一个字母只能被一个单词使用，比如走了一个词apple, 那么a, p, p,
: l, e这几个char的位置不能再被其它单词用了。
: 补充：看题意一个单词应该是由board中连续的字母组成的。除了brute force想不到啥
: 好方法，大牛们能指点下么？
|
l******8
发帖数: 1691 | 12 也就直接dfs吧。
p,
【在 c*****m 的大作中提到】
: 看两个A家面经里面有这题:
: 给你一个board, 一个dict让你计算最多能有多少个valid单词出现在这个Board上面。
: 限制是board中的一个字母只能被一个单词使用，比如走了一个词apple, 那么a, p, p,
: l, e这几个char的位置不能再被其它单词用了。
: 补充：看题意一个单词应该是由board中连续的字母组成的。除了brute force想不到啥
: 好方法，大牛们能指点下么？
|
f*****s
发帖数: 219 | 13 这个算Brutal force吗？
★ 发自iPhone App: ChineseWeb 1.0.6
【在 I******c 的大作中提到】
: leecode上的word search I/II说白了就是backtracking/穷举嘛。这道题也可以用嘛
: 把每个词在board上的位置记下来（如果这个词存在于board上的话）。然后就
: backtracking每个词。如果一个词在board上有多个的可能，那试的时候就把多个可能
: 都试一下。
|
