【leetcode】【100268. 最长公共后缀查询】【Trie树】

How to slove this problem?

1. If we reverse the strings, the problem changes to finding the longest common prefix.
2. Build a Trie, each node is a letter and only saves the best word’s index in each node, based on the criteria
3. .code:

   class Solution {
       public Node ROOT;
       public String[] wordsContainer;
       public static final char INVALID = '1';
       public int minIndex = 1000_000_000;
       public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
           this.wordsContainer = new String[wordsContainer.length];
           minIndex = 1000_000_000;
           int minlen = 1000_000_000;
           for (int i = 0; i < wordsContainer.length; i++) {
               this.wordsContainer[i] = new StringBuilder(wordsContainer[i]).reverse().toString();
               if (minlen > wordsContainer[i].length()) {
                   minlen = wordsContainer[i].length();
                   minIndex = i;
               }
           }
   
           ROOT = new Node(INVALID, minIndex);
   
           for (int i = 0; i < this.wordsContainer.length; i++) {
               buildTree(this.wordsContainer[i], i);
           }
           int[] ans = new int[wordsQuery.length];
           for (int i = 0; i < wordsQuery.length; i++) {
               String query = new StringBuilder(wordsQuery[i]).reverse().toString();
               ans[i] = getIndex(query);
           }
           return ans;
       }
   
       public int getIndex(String query) {
           int treeId = query.charAt(0) - 'a';
           Node tree = ROOT.children[treeId];
           if (tree == null) {
               return minIndex;
           }
           int ans = tree.index;
           Node curr = tree;
           for (int j = 1; j < query.length(); j++) {
               Node next = curr.children[query.charAt(j)-'a'];
               if( next != null){
                   ans = next.index;
               }else{
                   return ans;
               }
               curr = next;
           }
           return ans;
       }
   
   
       public void buildTree(String str, int index) {
           int treeId = str.charAt(0) - 'a';
           Node[] trees = ROOT.children;
   
           if (trees[treeId] == null) {
               trees[treeId] = new Node(str.charAt(0), index);
           } else {
               int origin = trees[treeId].index;
               if (wordsContainer[origin].length() > str.length()) {
                   trees[treeId].index = index;
               }
           }
   
           Node root = trees[treeId];
           Node curr = root;
   
           for (int j = 1; j < str.length(); j++) {
               Node existNode = curr.children[str.charAt(j) - 'a'];
               if (existNode != null) {
                   existNode.index = wordsContainer[existNode.index].length() > str.length() ? index : existNode.index;
               } else {
                   existNode = new Node(str.charAt(j), index, curr);
               }
               curr.children[str.charAt(j) - 'a'] = existNode;
               curr = existNode;
           }
       }
   
       class Node {
           char letter;
           int index;
           Node parent;
           Node[] children;
           public Node(char letter, int index) {
               this.letter = letter;
               this.index = index;
               parent = null;
               children = new Node[26];
           }
   
           public Node(char letter, int index, Node parent) {
               this.letter = letter;
               this.index = index;
               this.parent = parent;
               children = new Node[26];
           }
       }
   }