Shortest Unique Prefix

Find shortest unique prefix to represent each word in the list.

Input: [zebra, dog, duck, dove]
Output: {z, dog, du, dov}
where we can see that
zebra = z
dog = dog
duck = du
dove = dov

Solution:

Time: O(n)
Space: O(n)

public class Solution {
    static class TrieNode {
        List<TrieNode> children;
        char c;
        int freq;
        
        public TrieNode(char c) {
            this.children = new ArrayList<>();
            this.c = c;
            this.freq = 1;
        }
    }
    
    static class Trie {
        TrieNode root;
        
        public Trie() {
            root = new TrieNode('\0');
        }
        
        public void insert(String s) {
            char[] arr = s.toCharArray();
            TrieNode curr = root;
            for (char c : arr) {
                boolean found = false;
                for (TrieNode child : curr.children) {
                    if (child.c == c) {
                        curr = child;
                        curr.freq ++;
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    TrieNode node = new TrieNode(c);
                    curr.children.add(node);
                    curr = node;
                }
            }
        }
        
        public String prefix(String s) {
            TrieNode curr = root;
            StringBuilder sb = new StringBuilder();
            char[] arr = s.toCharArray();
            for (char c : arr) {
                if (curr.children.size() == 1 && curr.children.get(0).freq == 1) {
                    break;
                }
                sb.append(c);
                for (TrieNode child : curr.children) {
                    if (child.c == c) {
                        curr = child;
                        break;
                    }
                }
            }
            return sb.toString();
        }
    }
    
    public ArrayList<String> prefix(ArrayList<String> A) {
        Trie trie = new Trie();
        ArrayList<String> result = new ArrayList<>();
        for (String s : A) {
            trie.insert(s);
        }
        for (String s : A) {
            result.add(trie.prefix(s));
        }
        return result;
    }
}