e******0 发帖数: 291 | 1 给出16 characters(可能有重复的), 求在4*4的Grid上输出 valid words. (即每行
每列都是valid 4字母单词)。 给了字典。
a / / /
/ / / /
/ / / /
/ / / / | D**********d 发帖数: 849 | 2 My 2 cents:
1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查
询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词
2. Grid 位置上字母可能出现在单词里的位置
1 & 1,2 & 1,3 & 1,4 \
1,2 & 2 & 2,3 & 2,4 \
1,3 & 3,2 & 3 & 3,4 \
1,4 & 4,2 & 4,3 & 4 \
然后用回溯 DFS, 就像解 Sukodu 一样 | l*n 发帖数: 529 | 3 电面问的啊?一个问题就覆盖好多内容。
【在 e******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给出16 characters(可能有重复的), 求在4*4的Grid上输出 valid words. (即每行 : 每列都是valid 4字母单词)。 给了字典。 : a / / / : / / / / : / / / / : / / / /
| e******0 发帖数: 291 | 4 他有提示用PREFIX来做。
但完全没有思路。
觉得应该和SUKUDU的思路一样。
【在 D**********d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : My 2 cents: : 1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查 : 询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词 : : 2. Grid 位置上字母可能出现在单词里的位置 : 1 & 1,2 & 1,3 & 1,4 \ : 1,2 & 2 & 2,3 & 2,4 \ : 1,3 & 3,2 & 3 & 3,4 \ : 1,4 & 4,2 & 4,3 & 4 \ : 然后用回溯 DFS, 就像解 Sukodu 一样
| l*n 发帖数: 529 | 5 prefix就是用来check viability的吧,楼上说的没错,还是sodoku的思路。
就是找个空位扔一个未用的字符进去,然后check每个方向是否有希望成为单词,也就
是看的当前字符构成的prefix。但凡判定有人不能延伸为单词,就backtrack。
【在 e******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他有提示用PREFIX来做。 : 但完全没有思路。 : 觉得应该和SUKUDU的思路一样。
| e******0 发帖数: 291 | 6 我觉得 根据字典里四字词建立 Trie树, 四层 每层 16(如果有重复的字符就会小于
16), 共 16^4。 然后通过Trie 树, 来做validation 和 backtracking。
是这样的吗?
这样空间复杂度 和 时间复杂度 岂不是特别特别大?
谢谢。
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : prefix就是用来check viability的吧,楼上说的没错,还是sodoku的思路。 : 就是找个空位扔一个未用的字符进去,然后check每个方向是否有希望成为单词,也就 : 是看的当前字符构成的prefix。但凡判定有人不能延伸为单词,就backtrack。
| l*n 发帖数: 529 | 7 真实现的话,我觉得不用上trie,因为单词都不长,不如直接搞一个字母、2字母、3字
母、四字母的hashtable。最差情况也就是把词典size*4而已。
【在 e******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得 根据字典里四字词建立 Trie树, 四层 每层 16(如果有重复的字符就会小于 : 16), 共 16^4。 然后通过Trie 树, 来做validation 和 backtracking。 : 是这样的吗? : 这样空间复杂度 和 时间复杂度 岂不是特别特别大? : 谢谢。
| n****e 发帖数: 678 | 8 能问一下,为什么Trie树每层16?
【在 e******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得 根据字典里四字词建立 Trie树, 四层 每层 16(如果有重复的字符就会小于 : 16), 共 16^4。 然后通过Trie 树, 来做validation 和 backtracking。 : 是这样的吗? : 这样空间复杂度 和 时间复杂度 岂不是特别特别大? : 谢谢。
| e******0 发帖数: 291 | 9 我是根据DreamingBird大牛的大作想的。
就我的理解,DreamingBird 提出的思路是每层26,是因为26个字母。
题目中已经给出16个字母(有重复), 那么其实每层16就应该OK了。
这只是我的想法。
欢迎指教~~~~
【在 n****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能问一下,为什么Trie树每层16?
| n**********e 发帖数: 45 | 10 感觉预处理字典挺麻烦的,如果字典很大呢?
试贴一简单解法:
bool check(unordered_set& dict, char *a, int i) {
// a[] is a permutation of the char set
// based on the elements a[0]-a[i], check if a[] a could be a solution.
int N = 4, k= (i+1)/N; // k: complete line number
string s(a,a+N*N);
for (int l = 0; l
if ( dict.find(s.substr(l*N,N)) == dict.end() ) return false;
if (k==N-1) { // check columns
for(int n= 0; n < (i+1)%N; n++) {
string t("");
for (int l=0; l
t = t + s[n*N+l];
if( dict.find(t) == dict.end() ) return false;
}
}
return true;
}
// i starts with -1 when calling
//
char *wordgrid(unordered_set& dict, char *a, int i) {
int N = 4; // 4x4 grid
if (!check(dict,a,i)) return NULL;
if (i == N*N-1)
if (check(dict,a,i)) {
char *p = new char [N*N];
for( int k=0; k
return p;
}
i++;
for( int k = i; k
char *p = new char [N*N];
for (int l=0; l
swap( p[i],p[k]);
char *q = wordgrid(dict,p, i);
delete [] p;
if (q!=NULL) return q;
}
return NULL;
} | | | e******0 发帖数: 291 | 11 给出16 characters(可能有重复的), 求在4*4的Grid上输出 valid words. (即每行
每列都是valid 4字母单词)。 给了字典。
a / / /
/ / / /
/ / / /
/ / / / | D**********d 发帖数: 849 | 12 My 2 cents:
1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查
询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词
2. Grid 位置上字母可能出现在单词里的位置
1 & 1,2 & 1,3 & 1,4 \
1,2 & 2 & 2,3 & 2,4 \
1,3 & 3,2 & 3 & 3,4 \
1,4 & 4,2 & 4,3 & 4 \
然后用回溯 DFS, 就像解 Sukodu 一样 | l*n 发帖数: 529 | 13 电面问的啊?一个问题就覆盖好多内容。
【在 e******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给出16 characters(可能有重复的), 求在4*4的Grid上输出 valid words. (即每行 : 每列都是valid 4字母单词)。 给了字典。 : a / / / : / / / / : / / / / : / / / /
| e******0 发帖数: 291 | 14 他有提示用PREFIX来做。
但完全没有思路。
觉得应该和SUKUDU的思路一样。
【在 D**********d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : My 2 cents: : 1. 根据字典里四字词建立 Trie: 四层 每层 26, 共 26^4, O(1)。这样使得像以下查 : 询为 O(1): 是否存在第三个字母为 X? 是否存在 ABC 为前缀的单词 : : 2. Grid 位置上字母可能出现在单词里的位置 : 1 & 1,2 & 1,3 & 1,4 \ : 1,2 & 2 & 2,3 & 2,4 \ : 1,3 & 3,2 & 3 & 3,4 \ : 1,4 & 4,2 & 4,3 & 4 \ : 然后用回溯 DFS, 就像解 Sukodu 一样
| l*n 发帖数: 529 | 15 prefix就是用来check viability的吧,楼上说的没错,还是sodoku的思路。
就是找个空位扔一个未用的字符进去,然后check每个方向是否有希望成为单词,也就
是看的当前字符构成的prefix。但凡判定有人不能延伸为单词,就backtrack。
【在 e******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他有提示用PREFIX来做。 : 但完全没有思路。 : 觉得应该和SUKUDU的思路一样。
| e******0 发帖数: 291 | 16 我觉得 根据字典里四字词建立 Trie树, 四层 每层 16(如果有重复的字符就会小于
16), 共 16^4。 然后通过Trie 树, 来做validation 和 backtracking。
是这样的吗?
这样空间复杂度 和 时间复杂度 岂不是特别特别大?
谢谢。
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : prefix就是用来check viability的吧,楼上说的没错,还是sodoku的思路。 : 就是找个空位扔一个未用的字符进去,然后check每个方向是否有希望成为单词,也就 : 是看的当前字符构成的prefix。但凡判定有人不能延伸为单词,就backtrack。
| l*n 发帖数: 529 | 17 真实现的话,我觉得不用上trie,因为单词都不长,不如直接搞一个字母、2字母、3字
母、四字母的hashtable。最差情况也就是把词典size*4而已。
【在 e******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得 根据字典里四字词建立 Trie树, 四层 每层 16(如果有重复的字符就会小于 : 16), 共 16^4。 然后通过Trie 树, 来做validation 和 backtracking。 : 是这样的吗? : 这样空间复杂度 和 时间复杂度 岂不是特别特别大? : 谢谢。
| n****e 发帖数: 678 | 18 能问一下,为什么Trie树每层16?
【在 e******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得 根据字典里四字词建立 Trie树, 四层 每层 16(如果有重复的字符就会小于 : 16), 共 16^4。 然后通过Trie 树, 来做validation 和 backtracking。 : 是这样的吗? : 这样空间复杂度 和 时间复杂度 岂不是特别特别大? : 谢谢。
| e******0 发帖数: 291 | 19 我是根据DreamingBird大牛的大作想的。
就我的理解,DreamingBird 提出的思路是每层26,是因为26个字母。
题目中已经给出16个字母(有重复), 那么其实每层16就应该OK了。
这只是我的想法。
欢迎指教~~~~
【在 n****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能问一下,为什么Trie树每层16?
| n**********e 发帖数: 45 | 20 感觉预处理字典挺麻烦的,如果字典很大呢?
试贴一简单解法:
bool check(unordered_set& dict, char *a, int i) {
// a[] is a permutation of the char set
// based on the elements a[0]-a[i], check if a[] a could be a solution.
int N = 4, k= (i+1)/N; // k: complete line number
string s(a,a+N*N);
for (int l = 0; l
if ( dict.find(s.substr(l*N,N)) == dict.end() ) return false;
if (k==N-1) { // check columns
for(int n= 0; n < (i+1)%N; n++) {
string t("");
for (int l=0; l
t = t + s[n*N+l];
if( dict.find(t) == dict.end() ) return false;
}
}
return true;
}
// i starts with -1 when calling
//
char *wordgrid(unordered_set& dict, char *a, int i) {
int N = 4; // 4x4 grid
if (!check(dict,a,i)) return NULL;
if (i == N*N-1)
if (check(dict,a,i)) {
char *p = new char [N*N];
for( int k=0; k
return p;
}
i++;
for( int k = i; k
char *p = new char [N*N];
for (int l=0; l
swap( p[i],p[k]);
char *q = wordgrid(dict,p, i);
delete [] p;
if (q!=NULL) return q;
}
return NULL;
} | | | D**********d 发帖数: 849 | 21 是每层最多 16, 因为不在给的 16 个字母里的 单词不用考虑
【在 e******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我是根据DreamingBird大牛的大作想的。 : 就我的理解,DreamingBird 提出的思路是每层26,是因为26个字母。 : 题目中已经给出16个字母(有重复), 那么其实每层16就应该OK了。 : 这只是我的想法。 : 欢迎指教~~~~
| l*******g 发帖数: 82 | 22 把字典用suffix tree存放。
给出16 characters(可能有重复的), 求在4*4的Grid上输出 valid words. (即每行
每列都是valid 4字母单词)。 给了字典。a / / / ........
【在 e******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给出16 characters(可能有重复的), 求在4*4的Grid上输出 valid words. (即每行 : 每列都是valid 4字母单词)。 给了字典。 : a / / / : / / / / : / / / / : / / / /
| t********e 发帖数: 12 | 23 电面考这个就是不让人过的意思?onsite这也算是大招了吧。 | t********e 发帖数: 12 | 24 大概是trie+backtrace+hashtable...
建立trie是为了按prefix快速查找。
backtrace from 0 to 3, at each step i, fill in row i and col i at the same
time. chars before i are already determined, and char at i must be the same.
create hash table to group candidates from row i and col i that char i are
equal. test and keep going down or backtrace.
for example, suppose we are at level 2. we have
x x A x
x x B x
C D = ?
x x ? ?
'x's and A/B/C/D are the chars we already fill out.
at level 2, all information we know is:
1. row 2 must be a word AB..
2. col 2 must be a word CD..
3. the third char of the two word must be equal
so we find all {AB..} and {CD..} from tree, and group them by hashing third
char. so we have
u-> {ABu.} {CDu.}
v-> {ABv.} {CDv.}
......
each combination from 2 sets for a hash key need to be tested. | y*****3 发帖数: 451 | 25 请问这道题怎么解?过几天就要groupon goods电面了,求解法。。谢谢!
【在 e******0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给出16 characters(可能有重复的), 求在4*4的Grid上输出 valid words. (即每行 : 每列都是valid 4字母单词)。 给了字典。 : a / / / : / / / / : / / / / : / / / /
|
|