Accepted recursive solution using Trie Tree


  • 9
    Z

    The idea is quite simple. Just use a trie tree to accelerate testing whether a substring is valid. The value of each TrieNode is used to deal with duplication and to mark whether the word is used before.

          static class TrieNode {
               int value = 0;
               Map<Character, TrieNode> children = new HashMap<Character, TrieNode>();
           }
    
           TrieNode trie;
    
        // build a trie tree
        public List<Integer> findSubstring(String S, String[] L) {
            trie = buildTrie(L);
            int length = getTotalLength(L);
            List<Integer> result = new LinkedList<Integer>();
            for (int i = 0; i < S.length() - length + 1; i++) {
                if (isSubString(S, i, i + length))
                    result.add(i);
            }
            return result;
        }
        
        private int getTotalLength(String[] L) {
            int sum = 0;
            for (String l : L)
                sum += l.length();
            return sum;
        }
        
        private TrieNode buildTrie(String[] L) {
            TrieNode root = new TrieNode();
            for (String l : L)
                addWord(root, l);
            return root;
        }
        
        private void addWord(TrieNode root, String s) {
            TrieNode node = root;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                TrieNode next = node.children.get(c);
                if (next == null) {
                    next = new TrieNode();
                    node.children.put(c, next);
                }
                node = next;
            }
            node.value++;
        }
        
        private boolean isSubString(String S, int start, int end) {
        	if (start == end)
        		return true;
            // search in the trie tree
            TrieNode node = trie;
            for (int i = start; i < end; i++) {
                char c = S.charAt(i);
                if (node.children.get(c) == null)
                    return false;
                node = node.children.get(c);
                if (node.value > 0) {  // leaf & can be used
                    node.value--; // mark as used
                    if (isSubString(S, i + 1, end)) {
                        node.value++; // mark as unused
                        return true;
                    }
                    node.value++; // mark as unused
                }
            }
            return false;
        }

  • 1
    M

    Thanks for sharing! Follow your idea and write a C++ version, 76ms. Char has its own index, maybe array is better than hashmap,

    class TrieNode{
    public:    
        TrieNode* child[26];
        int cnt;   
        TrieNode(): cnt(0){
            memset(child, NULL, sizeof(TrieNode*)*26);
        }
    };
    
    class Trie{
        TrieNode* root;
    public:
        Trie(){
            root = new TrieNode();
        }
        TrieNode* getRoot(){
            return root;
        }
        void buildTrie(vector<string>& words){
            for (string w : words) {
                addWord(w);
            }
        }
        void addWord(string& word){
            TrieNode* cur=root;
            for(int i=0; i<word.size(); i++){
                int idx=word[i]-'a';
                if(cur->child[idx]==NULL){
                    cur->child[idx]=new TrieNode();
                }
                cur=cur->child[idx];
            }
            cur->cnt++;
        }
    };
       
    class Solution {
    public:
        Trie* trie;
        vector<int> findSubstring(string s, vector<string>& words) {
            trie= new Trie();
            trie->buildTrie(words);
            int length = 0;
            for (string w : words) {
                length += w.length();
            }
    
            vector<int> result;
            for (int i = 0; i < s.length() - length + 1; i++) {
                if (isSubString(s, i, i + length))
                    result.push_back(i);
            }
            return result;
        }
        bool isSubString(string& s, int start, int end) {
            TrieNode* node = trie->getRoot();
            int idx;
            for (int i = start; i < end; i++) {
                idx = s[i]-'a';
                if (node->child[idx] == NULL) return false;
                node = node->child[idx];
                if(node->cnt>0){
                    node->cnt--; // mark as used
                    if (i + 1==end || isSubString(s, i + 1, end)) {
                        node->cnt++; // mark as unused
                        return true;
                    }
                    node->cnt++; // mark as unused
                }
            }
            return false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.