d***2
发帖数: 7 | 1 题目是这样，26个字母，不重复取任意次（当然，必须<=26）组成一word；再由这样的
words组成file。
现给任意一个word (W1)和一file，要求在file中找另一word (W2), 且W1和W2没有相同
字母。（如果存
在多个W2，只需返回任意一个；若不存在，返回空。）
另一拓展问题：再recursive 地在file中找W3, W4……要求互相都没交集。
先谢过各位。 | a******e
发帖数: 982 | 2 Treat each word as a set instead of a sequence.
Then the universal word is the set with 26 letters.
You can find complement set of W1.
If each time you're given the word and the file, then
no preprocessing is needed. just linearly check each
word in the file and see if any of them is a subset
of comp(W1). This is O(n).
If the file is fixed and need to be check against
many words, then you can build a prefix tree for it.
Again, treat them as sets. For example, word "xad"
should be indexed as "ad | l********l
发帖数: 4 | 3 I assume you want W1, W2, W3... all have no shared characters.
There are maximum 26 words in this sequence.
Input: W1 (the word), Dictionary
steps:
boolean appeared[26]= new boolean[26];
for (char ch : W1)
appeared[ch] = true;
For (String word : Dictionary) {
goodWord = true;
for (char ch : word) {
if (appeared[ch]) {
goodWord = false;
break;
}
|
|
