C++ Iterative Solution based on iterators.


  • 0
    S

    My basic idea is just like a lot of other implementations: create a Trie where each branch represents a letter in the string, and use recursion to add and search words. However, unlike most other implementations that rely on passing a substring in each recursive call (which is very inefficient), or passing in the index of the current number, my program uses string::iterator, which gives the implementation a slightly more C++-flavored style.

    class WordDictionary {
    class TrieNode {
    public:
        bool isEnd;
        TrieNode* children[26];
        TrieNode(): isEnd(false) {
            for (int i = 0; i < 26; ++i) {
                children[i] = nullptr;
            }
        }
    };
    
    void addWordHelper(string::iterator strBeg, string::iterator strEnd, TrieNode* cur) {
        if (strBeg==strEnd) {   // When we reach the last char of the string
            cur->isEnd = true; return;  // mark the current node as a word's end
        }
        int char_ind =  *strBeg - 'a';
        
        // If the branch corresponding to this first char is not established yet
        if (cur->children[char_ind] == nullptr) 
            cur->children[char_ind] = new TrieNode(); // then create that node
        
        // then recursively add the rest of the string
        cur = cur->children[char_ind];
        addWordHelper(strBeg+1, strEnd, cur);
    }
    
    bool searchWordHelper(string::iterator strBeg, string::iterator strEnd, TrieNode* cur) {
        // If we reach the end of the string, see if the current node is a word's end
        if (strBeg==strEnd) return cur->isEnd;
        
        int char_ind = *strBeg - 'a';
        int nbeg = char_ind, nend = char_ind;      // The range of the child nodes to check. 
        if (*strBeg == '.') {
            nbeg = 0; nend = 25;    // '.' means to check all the 26 children.
        }
        
        // If any subTrie in the checking range contains the substring, then report true
        for (int i = nbeg; i <= nend; i++) {
            if (cur->children[i] && searchWordHelper(strBeg+1, strEnd, cur->children[i])) {
                return true;
            }
        }
        return false;
    }
    
    public:
    TrieNode root;
    
    // Adds a word into the data structure.
    void addWord(string word) {
        addWordHelper(word.begin(), word.end(), &root);    
    }
    
    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return searchWordHelper(word.begin(), word.end(), &root);
    }
    
    };

  • 0
    C

    The use of nbeg and nend is necessary ?
    It only switch between two pairs of values.

    if '.' => 0, 25

    else => char position

    below is my version of searchWordHelper which use pattern and pos to keep track next position to match in the recursive call stack.

      bool search_(const string& pattern, TrieNode* nptr, int pos=0) {
        if (pos< pattern.length()) {
          const char c = pattern[pos];
          int idx = c-'a' ;
          if (c!='.') {
    	    if (nptr->_links[idx]) {
    	        return search_(pattern, nptr->_links[idx], pos+1);
    	     }
    	    else {
    	        return false;
    	    }
          }
          else {
    	    for (int i=0; i<26; ++i) {
    	        if (nptr->_links[i] && search_(pattern, nptr->_links[i], pos+1))
    	            return true;
    	    }
    	    return false;
          }
        }
        else {
          return nptr->_valid;
        }
      }
    

Log in to reply
 

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