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 的大作中提到】
: 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
: 每列都是valid 4字母单词)。 给了字典。
: a / / /
: / / / /
: / / / /
: / / / /
| e******0
发帖数: 291 | 4 他有提示用PREFIX来做。
但完全没有思路。
觉得应该和SUKUDU的思路一样。
【在 D**********d 的大作中提到】
: 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 的大作中提到】
: 他有提示用PREFIX来做。
: 但完全没有思路。
: 觉得应该和SUKUDU的思路一样。
| e******0
发帖数: 291 | 6 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
是这样的吗？
这样空间复杂度 和 时间复杂度 岂不是特别特别大？
谢谢。
【在 l*n 的大作中提到】
: prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
: 就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
: 是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。
| l*n
发帖数: 529 | 7 真实现的话，我觉得不用上trie，因为单词都不长，不如直接搞一个字母、2字母、3字
母、四字母的hashtable。最差情况也就是把词典size*4而已。
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
| n****e
发帖数: 678 | 8 能问一下，为什么Trie树每层16？
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
| e******0
发帖数: 291 | 9 我是根据DreamingBird大牛的大作想的。
就我的理解，DreamingBird 提出的思路是每层26，是因为26个字母。
题目中已经给出16个字母（有重复）， 那么其实每层16就应该OK了。
这只是我的想法。
欢迎指教~~~~
【在 n****e 的大作中提到】
: 能问一下，为什么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 的大作中提到】
: 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
: 每列都是valid 4字母单词)。 给了字典。
: a / / /
: / / / /
: / / / /
: / / / /
| e******0
发帖数: 291 | 14 他有提示用PREFIX来做。
但完全没有思路。
觉得应该和SUKUDU的思路一样。
【在 D**********d 的大作中提到】
: 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 的大作中提到】
: 他有提示用PREFIX来做。
: 但完全没有思路。
: 觉得应该和SUKUDU的思路一样。
| e******0
发帖数: 291 | 16 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
是这样的吗？
这样空间复杂度 和 时间复杂度 岂不是特别特别大？
谢谢。
【在 l*n 的大作中提到】
: prefix就是用来check viability的吧，楼上说的没错，还是sodoku的思路。
: 就是找个空位扔一个未用的字符进去，然后check每个方向是否有希望成为单词，也就
: 是看的当前字符构成的prefix。但凡判定有人不能延伸为单词，就backtrack。
| l*n
发帖数: 529 | 17 真实现的话，我觉得不用上trie，因为单词都不长，不如直接搞一个字母、2字母、3字
母、四字母的hashtable。最差情况也就是把词典size*4而已。
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
| n****e
发帖数: 678 | 18 能问一下，为什么Trie树每层16？
【在 e******0 的大作中提到】
: 我觉得 根据字典里四字词建立 Trie树， 四层 每层 16（如果有重复的字符就会小于
: 16）, 共 16^4。 然后通过Trie 树， 来做validation 和 backtracking。
: 是这样的吗？
: 这样空间复杂度 和 时间复杂度 岂不是特别特别大？
: 谢谢。
| e******0
发帖数: 291 | 19 我是根据DreamingBird大牛的大作想的。
就我的理解，DreamingBird 提出的思路是每层26，是因为26个字母。
题目中已经给出16个字母（有重复）， 那么其实每层16就应该OK了。
这只是我的想法。
欢迎指教~~~~
【在 n****e 的大作中提到】
: 能问一下，为什么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 的大作中提到】
: 我是根据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 的大作中提到】
: 给出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 的大作中提到】
: 给出16 characters（可能有重复的）， 求在4*4的Grid上输出 valid words. (即每行
: 每列都是valid 4字母单词)。 给了字典。
: a / / /
: / / / /
: / / / /
: / / / /
|
|
