首页 > itarticle > leetcode 211. add and search word Trie+回溯算法

leetcode 211. add and search word Trie+回溯算法

admin 11月 12, 2020 0

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

Trie+回溯算法

本题为了实现方便采用静态分配法，详细的Trie树可以见我的另一篇博客，回溯可以参考博客

C++代码

typedef struct trie_node {
    bool valid;
    struct trie_node* next[26];
}TrieNode, *Trie;

TrieNode* createTrieNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    node->valid = false;
    memset(node->next, NULL, sizeof(node->next));
    return node;
}

class WordDictionary {
public:
    Trie root = createTrieNode();
    
    // Adds a word into the data structure.
    void addWord(string word) {
        if (word.length() <= 0) {
            return;
        }
        int len = word.length();
        TrieNode* p = root;
        for (int i = 0; i < len; i++) {
            if (p->next[word[i] - 'a'] == NULL) {
                p->next[word[i] - 'a'] = createTrieNode();
            }
            p = p->next[word[i] - 'a'];
        }
        p->valid = true;
    }

    // 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) {
        if (word.length() <= 0) {
            return false;
        }
        int len = word.length();
        TrieNode* p = root;
        for (int i = 0; i < len; i++) {
            if (word[i] != '.') {
                if (p->next[word[i] - 'a'] == NULL) {
                    return false;
                }
                else {
                    p = p->next[word[i] - 'a'];
                }
            }
            else {
                return backTrace(p, word, i);
            }
        }
        return p->valid;
    }
    
    bool backTrace(Trie p, string word, int depth) {
        int len = word.length();
        if (len <= 0) {
            return true;
        }
        TrieNode* p_save;
        for (int j = 0; j < 26; j++) {
            if (p->next[j] != NULL) {
                p_save = p;
                p = p->next[j];
                bool check = true;
                
                for (int i = depth+1; i < len; i++) {
                    if (word[i] != '.') {
                        if (p->next[word[i] - 'a'] == NULL) {
                            check = false;
                            break;
                        }
                        else {
                            p = p->next[word[i] - 'a'];
                        }
                    }
                    else {
                         if (backTrace(p, word, i)) {
                             return true;
                         }
                         else {
                             check = false;
                             break;
                         }
                    }
                }
                if (check && p->valid) {
                    return true;
                }
                else {
                    p = p_save;
                }
            }
        }
        return false;
    }
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

Bug Free Procedure 从记事本直接写代码