Longest Common Prefix LeetCode solution in Java

1
class TrieNode {
2
  TrieNode[] childs;
3
  int frequency;
4

5
  TrieNode() {
6
    childs = new TrieNode[26];
7
    this.frequency = 1;
8
  }
9
}
10

11
class Solution {
12

13
  TrieNode root = new TrieNode();
14

15
  public String longestCommonPrefix(String[] strs) {
16
    if (strs.length == 0) return "";
17
    if (strs.length == 1) return strs[0];
18
    for (String str : strs) {
19
      insertIntoTrie(str.toLowerCase());
20
    }
21
    return findCommonPrefix(strs[0], strs.length);
22
  }
23

24
  private void insertIntoTrie(String str) {
25
    TrieNode ptr = root;
26
    for (int i = 0; i < str.length(); i++) {
27
      if (ptr.childs[str.charAt(i) - 'a'] == null) {
28
        ptr.childs[str.charAt(i) - 'a'] = new TrieNode();
29
      } else {
30
        ptr.childs[str.charAt(i) - 'a'].frequency++;
31
      }
32
      ptr = ptr.childs[str.charAt(i) - 'a'];
33
    }
34
  }
35

36
  private String findCommonPrefix(String str, int n) {
37
    String ans = "";
38
    for (int i = 0; i < str.length(); i++) {
39
      if (root.childs[str.charAt(i) - 'a'].frequency != n) {
40
        return ans;
41
      }
42
      ans += str.charAt(i);
43
      root = root.childs[str.charAt(i) - 'a'];
44
    }
45
    return ans;
46
  }
47
}