Trie implementation for left to right wildcard search
Eclipse says that the second null check in the search method is dead code:

if (current == null) {
    return matches;
}


Furthermore, it could be refactored to the following:

public Set&lt;Trie&gt; search(final String word) {
    count = 0;
    Trie current = this;
    for (final Character c: word.toCharArray()) {
        ++count;
        current = current.children.get(c);
        if (current == null) {
            return Collections.emptySet();
        }
    }
    return current.connections;
}

You should specify the return types:

public Set&lt;Trie&gt; search(final String word) { ... }
public Set&lt;Trie&gt; build() {... }


instead of 

public Set search(final String word) { ... }
public Set build() {... }

Consider using 


StringUtils.isBlank instead of the (word == null || "".equals(word.trim())) and
StringUtils.isNotEmpty instead of (this.word != null &amp;&amp; this.word.length() &gt; 0). 


I've found them more readable.
If I'm right you could iterate over the values directly in the build method:

for (final Trie childTrie: children.values()) {
    connections.addAll(childTrie.build());
}

I'd separate the builder logic from the Trie class. Currently clients can easily misuse this class:

t.build();
t.add("can2");


(Effective Java, 2nd Edition, Item 2: Consider a builder when faced with many constructor parameters)
connections does not seem a good name. It took some time to figure out that this set contains the descendant Trie objects which has a word. I might call it descendantsWithWord. Furthermore, it could contain only the words (strings), not the Trie objects, so it could be simply Set&lt;String&gt; descendantWords.
The static count field does not smells well. It is used for two different purposes. I'd create a createdTrieObjects field:

private int createdTrieObjects = 1;


and increment it in the add method:

t.children.put(c, new Trie());
createdTrieObjects++;


On the other hand, in the search method you could return a SearchResult object which contains the search depth (it's the count currently) and the result strings:

public class SearchResult {

    private final Set&lt;String&gt; words;
    private final int searchDepth;

    ...

}


It contains only a set of string instead of the Set&lt;Trie&gt; collection. I think clients should not know about the internal Trie objects. If you don't need the search depth return with Set&lt;String&gt; only:

public Set&lt;String&gt; search(final String wordStart) {
    Trie current = this;
    for (final Character c: wordStart.toCharArray()) {
        current = current.children.get(c);
        if (current == null) {
            return Collections.emptySet();
        }
    }
    return Collections.unmodifiableSet(current.descendantWords);
}


Please note the Collections.unmodifiableSet call. It prohibits malicious clients to modify the Trie's internal structure. (Effective Java, 2nd Edition, Item 39: Make defensive copies when needed)
You could eliminate the build method and the word field if you fill the descendantWords in the add method:

 public void add(final String word) {
    checkArgument(StringUtils.isNotBlank(word), "word can not be blank");
    Trie current = this;
    descendantWords.add(word);
    for (final Character c: word.toCharArray()) {
        if (!current.children.containsKey(c)) {
            current.children.put(c, new Trie());
            createdTrieObjects++;
        }
        current = current.children.get(c);
        current.descendantWords.add(word);
    }
}



Some small notes about the edit:


Instead of the checked IllegalAccessException I'd throw runtime IllegalStateException. It's rather a programming error if a client tries to add new element to a built trie.  (Effective Java, 2nd Edition, Item 58: Use checked exceptions for recoverable conditions and runtime exceptions for programming errors)
About the s variable in the search method: Try to minimize the scope of local variables. It's not necessary to declare them at the beginning of the method, declare them where they are first used. (Effective Java, Second Edition, Item 45: Minimize the scope of local variables)
You could copy the descendantsWithWord set with the HashSet's constructor instead of the for loop in the search method:

return new HashSet&lt;String&gt;(current.descendantWords);

The isBuilt flag should be at the beginning of the class with the other fields.


Here is the refactored version:

import java.util.Collections;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.apache.commons.lang3.StringUtils;

import static com.google.common.base.Preconditions.*;

public class Trie {

    private final Map&lt;Character, Trie&gt; children = new HashMap&lt;Character, Trie&gt;();
    private final Set&lt;String&gt; descendantWords = new HashSet&lt;String&gt;();

    public Trie() {
    }

    public void add(final String word) {
        checkArgument(StringUtils.isNotBlank(word), "word can not be blank");
        Trie current = this;
        descendantWords.add(word);
        for (final Character c: word.toCharArray()) {
            if (!current.children.containsKey(c)) {
                current.children.put(c, new Trie());
            }
            current = current.children.get(c);
            current.descendantWords.add(word);
        }
    }

    public Set&lt;String&gt; search(final String wordStart) {
        checkNotNull(wordStart, "wordStart cannot be null");
        Trie current = this;
        for (final Character c: wordStart.toCharArray()) {
            current = current.children.get(c);
            if (current == null) {
                return Collections.emptySet();
            }
        }
        return Collections.unmodifiableSet(current.descendantWords);
    }
}




Edit for the comment:

In your original implementation there is a set (descendantsWithWord) in every node which refers to Trie objects. In this answer there is a set (descendantWords) in every level which refers to String objects. 

The size of the sets are the same, Strings (as well as other objects, like Tries) are on the heap, the set contains only references to objects, so it does not count if they are Strings, Tries or other Objects, there is no difference in memory consumption and there is no duplication. The only difference is the method where the trie builds the set and the generic type of the set (references in the set).

I'm not too familiar with tries and articles on the Wikipedia do not mention that trie nodes should or should not store each descendants (not just references to the nodes of the next level), so I'm not sure that this is "officially" a trie or not.

Anyway, if I'm right you need fast search, so memory consumption looks is secondary here. Precalculating and storing the result in a cache (i.e. descendantWords) seems a better solution that traversing a subtree and building strings from characters on every search request as you did it too.

Furthermore, I'd consider using a Map&lt;String, Set&lt;String&gt;&gt; structure:

c,      [can, cancel, cancer]
ca,     [can, cancel, cancer]
can,    [can, cancel, cancer]
canc,   [cancel, cancer]
cance,  [cancel, cancer]
cancel, [cancel]
cancer, [cancel]
...


It's very similar to the trie above since (1) the trie's nodes are the same as the keys in this map and (2) the values of the map are the same as the descendantWords set in the trie. An advantage could be a simpler implementation, especially with a Multimap from Guava:

public class AutoSuggestCache {

    private final SetMultimap&lt;String, String&gt; words = HashMultimap.create();

    public AutoSuggestCache() {
    }

    public void add(final String word) {
        checkArgument(StringUtils.isNotBlank(word), "word can not be blank");
        for (int endIndex = 0; endIndex &lt; word.length(); endIndex++) {
            final String wordStart = word.substring(0, endIndex);
            words.put(wordStart, word);
        }
    }

    public Set&lt;String&gt; search(final String wordStart) {
        checkNotNull(wordStart, "wordStart cannot be null");
        return Collections.unmodifiableSet(words.get(wordStart));
    }
}