给儿子写的笔试答案

比眉伴天荒 2024-04-17 05:32 29阅读 0赞

import java.util.Scanner;
    import java.util.List;
    import java.util.ArrayList;
    
    public class Main{
        private int SIZE = 26;
        private TrieNode root;  //字典树的根
        private List<String> l=new ArrayList<String>();
    
        public Main() {  //初始化字典树
            root = new TrieNode();
    
        }
    
        private class TrieNode {  //字典树节点
            private int num;//有多少字符通过这个节点.
            private TrieNode[] son;// 所有的儿子节点
            private boolean isEnd;//是不是最后一个节点
            private char val;// 节点的值
    
    
            TrieNode() {
                num = 1;
                son = new TrieNode[SIZE];
                isEnd = false;
    
            }
        }
    
        public void insert(String str) {  //在字典树中插入一个单词
            if (str == null || str.length() == 0) {
                return;
            }
            TrieNode node = root;
            char[] letters=str.toCharArray();
            for (int i = 0, len = str.length(); i < len; i++) {
                int pos = letters[i] - 'a';
                if (node.son[pos] == null) {
                    node.son[pos] = new TrieNode();
                    node.son[pos].val = letters[i];
                } else {
                    node.son[pos].num++;
                }
                node = node.son[pos];
            }
            node.isEnd = true;
        }
    
        // 在字典树中查找.
        public void search(String str) {
            if (str == null || str.length() == 0) {
                return ;
            }
            TrieNode node = root;
            char[] letters=str.toCharArray();
            for (int i = 0, len = str.length(); i < len; i++) {
                int pos = letters[i] - 'a';
                System.out.printf("%c",letters[i]);
                node=node.son[pos];
                if( node.num==1)
                    break;;
            }
        }
    
    
        private void go() {
    
            Scanner in = new Scanner(System.in);
            String s=in.nextLine();
            String[] str=s.split(",");
            int num=0;
                for(int i=0;i<str.length;i++){
                l.add(str[i]);
                insert(str[i]);
                num ++;
                }
            for(int i = 0; i < num; i++){
                //System.out.printf("%s ",l.get(i));
                search(l.get(i));
                if(i!=num-1){
    
                System.out.print(",");
                }
            }
    
        }
    
        public static void main(String[] args) {
    
            Main ma=new Main();
            ma.go();
    
        }
    }