前缀树（Java，附上通用版本和本题版本）

本题 增加了一个has方法 改了startswith方法

import java.util.*;
public class Substr {
    public static class Trie {
        private final int ALPHABET_SIZE = 26;
        private Trie[] children = new Trie[ALPHABET_SIZE];
        boolean isEndOfWord = false;
        public Trie() {}

        public void insert(String word) {
            Trie tmp = this;
            for (char i : word.toCharArray()) {
                if (tmp.children[i-'a'] == null) {
                    tmp.children[i-'a'] = new Trie();
                }
                tmp = tmp.children[i-'a'];
            }
            tmp.isEndOfWord = true;
        }

        public boolean search(String word) {
            Trie tmp = this;
            for (char i : word.toCharArray()) {
                if (tmp.children[i-'a'] == null) {
                    return false;
                }
                tmp = tmp.children[i-'a'];
            }
            return tmp.isEndOfWord ? true : false;
        }

        public boolean startsWith(Trie tmp,String prefix) {
            for (char i : prefix.toCharArray()) {
                if (tmp.children[i-'a'] == null) {
                    return false;
                }
                tmp = tmp.children[i-'a'];
            }
            return true;
        }

        public boolean has(Trie tmp,String word){
            if(tmp.isEndOfWord == true) return false;
            Character c = word.charAt(0);
            boolean a = false;
            if(tmp.children[c - 'a'] != null){
                a = startsWith(tmp,word);
            }
            int temp = 0;
            for (int i = 0; i < 26; i++) {
                if(tmp.children[i] != null){
                    temp = i;
                    break;
                }
            }
            return a||has(tmp.children[temp],word);
        }
    }
    public boolean[] chkSubStr(String[] p, int n, String s) {
        // write code here
        Trie trie = new Trie();
        trie.insert(s);
        boolean[] res = new boolean[n];
        for (int i = 0; i < n; i++) {
            if(trie.has(trie,p[i])) res[i] = true;
        }
        return res;
    }
}

通用版本，实现了insert，search，startswith

public class Trie {
    private final int ALPHABET_SIZE = 26;
    private Trie[] children = new Trie[ALPHABET_SIZE];
    boolean isEndOfWord = false;
    public Trie() {}

    public void insert(String word) {
        Trie tmp = this;
        for (char i : word.toCharArray()) {
            if (tmp.children[i-'a'] == null) {
                tmp.children[i-'a'] = new Trie();
            }
            tmp = tmp.children[i-'a'];
        }
        tmp.isEndOfWord = true;
    }

    public boolean search(String word) {
        Trie tmp = this;
        for (char i : word.toCharArray()) {
            if (tmp.children[i-'a'] == null) {
                return false;
            }
            tmp = tmp.children[i-'a'];
        }
        return tmp.isEndOfWord ? true : false;
    }

    public boolean startsWith(String prefix) {
        Trie tmp = this;
        for (char i : prefix.toCharArray()) {
            if (tmp.children[i-'a'] == null) {
                return false;
            }
            tmp = tmp.children[i-'a'];
        }
        return true;
    }
}