https://www.lintcode.com/problem/identifying-strings

IdentifyString.java

public class Solution {
    /**
     * @param stringArray: a string array
     * @return: return every strings'short peifix
     */
    public String[] ShortPerfix(String[] stringArray) {
        // write your code here
        if (stringArray == null) {
            return new String[]{};
        }
        Trie trie = new Trie();
        for (String word: stringArray) {
            trie.add(word);
        }
        String[] minimalPrefix = new String[stringArray.length];
        for (int i = 0; i < minimalPrefix.length; i++) {
            minimalPrefix[i] = trie.minimalPrefix(stringArray[i]);
        }
        return minimalPrefix;
    }
}

final class Trie {
    private TrieNode root;
    
    Trie() {
        root = new TrieNode();
    }
    
    void add(String word) {
        TrieNode parent = root;
        
        for (int i = 0; i < word.length(); i++) {
            char character = word.charAt(i);
            TrieNode node;
            
            if (parent.children.containsKey(character)) {
                node = parent.children.get(character);
            } else {
                node = new TrieNode();
            }
            parent.children.put(character, node);
            
            node.wordCount++;
            parent = node;
        }
    }
    
    String minimalPrefix(String word) {
        StringBuilder builder = new StringBuilder();
        TrieNode parent = root;
        
        for (int i = 0; i < word.length(); i++) {
            char character = word.charAt(i);
            TrieNode node;
            
            if (!parent.children.containsKey(character)) {
                return "";
            }
            
            node = parent.children.get(character);
            builder.append(character);
            
            if (node.wordCount == 1) {
                return builder.toString();
            }
            
            parent = node;
        }
        
        if (!parent.isWord) {
            return "";
        }
        return builder.toString();
    }
    
    private final class TrieNode {
        boolean isWord;
        HashMap<Character, TrieNode> children;
        int wordCount;
        
        TrieNode() {
            children = new HashMap<>();
            wordCount = 0;
        }
    }
}