## Friday, October 5, 2012

### SRM268

Level 1 Level 2 Level 3
Div 1 Level 1 Level 2 Level 3
Div 2 Level 1 Level 2 Level 3

## Tutorials:

### Solution

For this problem, I use Trie data structure, when I tried to construct the tree, I could know if the word has 2 occurrences or not, if yes, added it to the list. otherwise, increase the counter, and continue; Check the comments in the code for detail.

### Source Code:

```import java.util.ArrayList;
import java.util.List;

/**
* @author: antonio081014
*
* @category: TopCoder, SRM268DIV1_250, SRM268DIV2_500.
* @solution: Use Trie to solve this problem. It takes O(NL), N is the number of
*            words in dict, and L is the length of the longest word.
*/
public class CmpdWords {

private List<String> list;

public void add(TrieNode root, String word, String origin) {
if (word.length() == 0) {
if (root.count < 0)
return;
root.count++;
// If this word's occurrence has more than 2 twice, which could be
// formed in two ways or it already has it in the dict;
if (root.count >= 2) {
// If this word is in the list, we should avoid counting it
// twice.
root.count = -1;
}
return;
}

int c = word.charAt(0) - 'a';
// Check the initialization is important!
if (root.next[c] == null)
root.next[c] = new TrieNode();
}

public int ambiguous(String[] dictionary) {
list = new ArrayList<String>();
TrieNode root = new TrieNode();
// Add the dict words into Trie, so if there is another combination
// string in the dict, the occurrence of that word would be 2;
for (int i = 0; i < dictionary.length; i++)
for (int i = 0; i < dictionary.length; i++) {
for (int j = 0; j < dictionary.length; j++) {
if (i != j) {
String tmp = dictionary[i] + dictionary[j];
}
}
}
return list.size();
}
}

class TrieNode {
public int count;
public TrieNode[] next;

public TrieNode() {
count = 0;
next = new TrieNode;
}

}
```

### Solution

The same as Div1_250 above;