SRM268

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

Tutorials:

---

Division One - Level Three:

Solution

Source Code:

---

Division One - Level Two:

Solution

Source Code:

---

Division One - Level One:

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 this word is already added to the ambiguous list;
     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) {
  list.add(origin);
  // 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();
 add(root.next[c], word.substring(1), origin);
    }

    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++)
     add(root, dictionary[i], dictionary[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];
      add(root, tmp, tmp);
  }
     }
 }
 return list.size();
    }
}

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

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

}

---

Sivision Two - Level Three:

Solution

Source Code:

---

Division Two - Level Two:

Solution

The same as Div1_250 above;

Source Code:

---

Division Two - Level One:

Solution

Source Code: