Java Trie Solution 
\n```\nclass Solution {\n    class TrieNode {\n        char c;\n        int end;\n        TrieNode[] children;\n        public TrieNode(char c) {\n            t
\n```\nclass Solution {\n    class TrieNode {\n        char c;\n        int end;\n        TrieNode[] children;\n        public TrieNode(char c) {\n            this.c = c;\n            this.end = 0;\n            this.children = new TrieNode[26];\n        }\n    }\n    public int numMatchingSubseq(String S, String[] words) {\n        if (words == null || words.length == 0) return 0;\n        TrieNode root = createTrie(words);\n        return dfs(S, root, 0);\n    }\n    \n    private TrieNode createTrie(String[] words) {\n        TrieNode root = new TrieNode(\'*\');\n        for (String word : words) {\n            addWord(root, word);\n        }\n        return root;\n    }\n    \n    private void addWord(TrieNode root, String word) {\n        for (char c : word.toCharArray()) {\n            if (root.children[c - \'a\'] == null) {\n                root.children[c - \'a\'] = new TrieNode(c);\n            }\n            root = root.children[c - \'a\'];\n        }\n        root.end++;\n    }\n    \n    private int dfs(String S, TrieNode root, int pos) {\n        if (root == null) return 0;\n        int index = S.indexOf(root.c, pos);\n        if (root.c != \'*\' && index == -1) return 0;\n        int res = root.end;\n        for (int i = 0; i < 26; i++) {\n            res += dfs(S, root.children[i], root.c == \'*\' ? 0 : index + 1);\n        }\n        return res;\n    }\n}
[]