S**I
发帖数: 15689 | 1 ☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 13:45:24 2012, 美东) 提到:
稍微扩展了一下。
Boggle game。从一个字符开始找邻居字符然后继续找，形成一个word。条件是，形成
了word之后要继续找，因为可能有更长的word。一旦用了一个字符以后，就不可以重复
使用了。
返回可以找到最多word情况的所有word。
更新一下：可以同时从不同的位置开始找，不一定只从一个字符开始。
☆─────────────────────────────────────☆
autumnworm (虫子，秋天的) 于 (Tue Jan 17 13:46:32 2012, 美东) 提到:
看起来好像是基本的背包问题吧。
☆─────────────────────────────────────☆
mark (花生，微爷远爷的爸爸) 于 (Tue Jan 17 14:08:07 2012, 美东) 提到:
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jan 17 14:08:14 2012, 美东) 提到:
Just a slight modification: Use a table to keep track of the used letters is
enough bah. Each time you deepen your DFS, mark the letter as visited, and
as you exit the DFS (ie, popping off the call stack), you un-mark the letter
as unvisited.
☆─────────────────────────────────────☆
mark (花生，微爷远爷的爸爸) 于 (Tue Jan 17 14:08:42 2012, 美东) 提到:
☆─────────────────────────────────────☆
kirit (Jack) 于 (Tue Jan 17 14:56:14 2012, 美东) 提到:
Use a trie to store dictionary and do recursive backtracking.
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 14:59:27 2012, 美东) 提到:
is
and
letter
我的思路是这样。找到所有可能的单词。就是通过你这个办法。最后的结果一定是这组
单词的某种组合。所以找单词的同时记录下来每个单词占用的字符位置。如果有N个单
词，先检查所有的N个单词看看有没有冲突。如果有，则假设最后结果有N-1个单词。看
有没有重突，然后检查N-2个单词。直到找到一组单词没有冲突的则是最后的解。
但是这样的话，面试的时候很难写代码呀。你的算法是从一个字符开始的其中一条路径
的，跟最后的解还存在很大的距离呀。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 14:59:45 2012, 美东) 提到:
能详细谈谈吗？
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 15:00:55 2012, 美东) 提到:
how to do recursive backtracking?
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jan 17 15:07:32 2012, 美东) 提到:
不，没那么复杂。基本逻辑这样，不知道对你的问题是否理解正确。
dfs(int row, int col,
char usedLetter[256],
char boggle[5][5],
bool visited[5][5], ...) {
if (row < 0 || row >= 5 || co < 0 || col >= 5) return;
if (visited[row][col]) return; // this cell is already visited
char currentLetter = boggle[row][col];
if (usedLetter[currentLetter]) return;
usedLetter[currentLetter] = true; // mark current letter as used.
// ... deepen DFS ...
visited[row][col] = false; // unamrk
usedLetter[currentLetter] = false; // unmark
}
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 15:11:54 2012, 美东) 提到:
是如果用到那个位置的字符，那个位置字符就不能用了。并不是这个字符的值不能用了
。你这个是从某一个位置的字符开始吧？然后call it for 所有的位置？ 但是最后的
解不一定是是这样的。
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jan 17 15:17:57 2012, 美东) 提到:
哦 看来我理解错了。这样子的确要麻烦些。
☆─────────────────────────────────────☆
ihasleetcode (1337coder) 于 (Tue Jan 17 15:30:43 2012, 美东) 提到:
感觉题目没说清楚。题目说如果找到word，要继续找最长的word，直到不能继续为止。
那这样会有冲突。例如：
p e n
b a i
c a b
上面的例子， "cabin" 和 "pen" 都共享‘n'字母，这种情况下，只能选择一个字，那
应该怎么定义选哪个呢？这样要看搜索顺序的先后吗？顺序又怎么定义呢？
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 15:42:11 2012, 美东) 提到:
题目就是让返回最多的单词数。cabin和pen选哪个，要看其他单词的情况。比如选了
cabin, 其他字符还能组成3个单词，而选了pen, 其他字符还能组成4个单词，那就选
pen了。
☆─────────────────────────────────────☆
kirit (Jack) 于 (Tue Jan 17 16:02:01 2012, 美东) 提到:
每次从一个格子（字母）开始，边走边mark。因为第一个字母不一样，所以word不重复
。全做完后，清掉所有mark，再以一下个格子的字母作为word的第一个字母，重复以上
过程。直到所有格子都作为第一个字母走过一遍。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 16:10:53 2012, 美东) 提到:
你怎么知道最后什么是最多的单词呢？比如你第一个格子得到N1个单词，然后得到N2，
一直到Nn。
这几个数都是以某点为起点的。但是最后的结果可能起点是很多个格子。而N1-Nn里边
的单词很多是冲突的。
☆─────────────────────────────────────☆
kirit (Jack) 于 (Tue Jan 17 16:21:04 2012, 美东) 提到:
每个格子的字母是互不相同的吧 -- 我的理解。For example,
char g[3][3]={{'a', 'b', 'e'},
{'c', 'd', 'f'},
{'g', 'h', 'l'}};
这样N1-Nn里的单词不会重复，因为首字母不同。
☆─────────────────────────────────────☆
viisa (viiiiiisa) 于 (Tue Jan 17 16:23:05 2012, 美东) 提到:
不就是一个8皇后么，搜就是了
没有更快的算法了
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 16:24:28 2012, 美东) 提到:
按题目来说有可能是重复的。字符是随机产生的。但是，你如果已经占用了那个位置的
字符，就不能重复使用了。
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Tue Jan 17 17:06:58 2012, 美东) 提到:
这个才是原题。递归。
☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 17:20:23 2012, 美东) 提到:
更新了一下题目。
☆─────────────────────────────────────☆
quantx (X矿工) 于 (Tue Jan 17 17:43:46 2012, 美东) 提到:
一个个找过去不就行了。你要多线程？
☆─────────────────────────────────────☆
autumnworm (虫子，秋天的) 于 (Wed Jan 18 00:19:56 2012, 美东) 提到:
俺的想法是，对串[start, end]考虑第N（属于[start, end]）个字符c,有3种情况。
把这个字符放前面
case1 = func(start, start+n) + func(start+n+1, end);
把这个字符放后面
case2 = func(start, start+n-1) + func(start+n, end);
两边都不放
case3 = func(start, start+n-1) + func(start+n+1, end) + (c is a word)?1:0;
结果是最大值。
return max(case1,case2,case3);
加上终止条件就是基本递推。然后加上查找表就是dp了。
☆─────────────────────────────────────☆
RyanReynolds (Ryan) 于 (Wed Jan 18 02:01:49 2012, 美东) 提到: |
|
