devbox
神奇cpp
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

字典树&前缀树 1 [Trie]

作者：神奇cpp | 2024-08-17 22:30:44

赞

踩

字典树&前缀树 1 [Trie]

1 字典树、前缀树、Trie

将一个单词列表使用words组装起来，实现如下：（仅含有小写的字典），可以在log(m)时间内查询一个单词是否在字典中。

1.1 可能的小技巧

  • 1 一些可以想到的优化：
    • 1.1 如果对一个长串反复查询，则使用一个node指针指向当前查询位于Trie里面的位置，避免反复查询相同的前缀
    • 1.2 如果对一个长串反复查询，尝试使用hash记录尾串的目标信息，避免对尾串反复查询
    • 1.3 逆序建树，构建后缀树等等，见本篇最后两个例子
class Trie {
public:
    vector<Trie *>curLevel;
    bool isEnd = false;

    Trie() : curLevel(26) {
        
    }

    void insert(string word) {
        Trie * curNode = this;
        for(char c : word) {
            c -= 'a';
            if(nullptr == curNode->curLevel[c]) {
                curNode->curLevel[c] = new Trie();
            } 
            // check nextLevel
            curNode = curNode->curLevel[c];
        }
        curNode->isEnd = true;
    }
    
    bool search(string word) {
        Trie * curNode = this;
        for(char c : word) {
            c -= 'a';
            if(nullptr == curNode->curLevel[c]) {
                return false;
            }
            curNode = curNode->curLevel[c];
        }
        return curNode->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie * curNode = this;
        for(char c : prefix) {
            c -= 'a';
            if(nullptr == curNode->curLevel[c]) {
                return false;
            }
            curNode = curNode->curLevel[c];
        }
        return true;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

2 例题

0212 单词搜索 II

1 题目

https://leetcode-cn.com/problems/word-search-ii

2 解题思路

  • 1 要搜索整个字母棋盘，很自然想到使用回溯
  • 2 要知道一个字符串是否在字典里，很自然想到trie
  • 3 具体解答方法
    • 3.1 如下代码的注释的backTrack函数很清晰的阐述啦思路，称之为old way
    • 3.2 old way的缺陷，对于tmpRes的前面的公共部分反复调用啦startWith函数重复计算啦，
    • 3.3 改进，使用curNode记录tmpRes在前缀树里面的位置，那么只需要根据curNode来判断tmpRes即将加入的新的字符是否为curNode的子节点就可以啦，提升了速度
class Solution {
public:
    class Trie {
    public:
        vector<Trie*> curLevel;
        bool isEnd = false;
        bool hasNext = true;
        Trie() : curLevel(26) {
        }

        void insert(string word) {
            Trie* curNode = this;
            for(char c : word) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    curNode->curLevel[c] = new Trie();
                }
                curNode = curNode->curLevel[c];
                curNode->hasNext = true;
            }
            curNode->isEnd = true;
        }

        bool inTrie(string word) {
            Trie* curNode = this;
            for(char c : word) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    return false;       
                }
                curNode = curNode->curLevel[c];
            }
            return curNode->isEnd;
        }

        bool startWith(string word) {
            Trie* curNode = this;
            for(char c : word) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    return false;       
                }
                curNode = curNode->curLevel[c];
            }
            return true;
        }

        bool endWith(string word) {
            Trie* curNode = this;
            for(char c : word) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    return false;       
                }
                curNode = curNode->curLevel[c];
            }
            return !curNode->hasNext;
        }
    };

    
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        int m = board.size();
        int n = board[0].size();
        
    
        
        // build trie in normal or reverse order
        // std::shared_ptr<Trie> treeNormal = make_shared<Trie>();
        Trie* treeNormal = new Trie();
        // std::unique_ptr<Trie> treeReverse = new Trie();
        for(auto w : words) {
            treeNormal->insert(w);
            // treeReverse.insert(reverse(w.begin(), w.end()));
        }

        int deltaX[] = {1, 0, -1, 0};
        int deltaY[] = {0, 1, 0, -1};
        // get the answer
        vector<string> res;
        unordered_set<string> hash;
        for(int i = 0; i < board.size(); ++i) {
            for(int j = 0; j < board[0].size(); ++j) {
                // std::cout << "check next st point!" << endl;
                string tmpRes = "";
                vector<vector<bool>> exploredFlag(m, vector<bool>(n, false));
                backTrack(i, j, board, tmpRes, res, treeNormal,
                    deltaX, deltaY, exploredFlag, hash
                );
            }
        }
        return res;
    }


/**
[["o","a","a","n"],
 ["e","t","a","e"],
 ["i","h","k","r"],
 ["i","f","l","v"]]
["oath","pea","eat","rain","oathi","oathk","oathf","oate","oathii","oathfi","oathfii"]
**/
    void backTrack(int i, int j, vector<vector<char>>& board, string& tmpRes, vector<string>& res, Trie* curNode, 
    const int* deltaX, const int* deltaY,
    vector<vector<bool>>& exploredFlag,
    unordered_set<string>& hash) {
        char ch = board[i][j];
        if(nullptr == curNode->curLevel[ch - 'a']) {
            return ;
        }

        // start from i, j
        tmpRes.push_back(board[i][j]);
        // Trie* lastNode = curNode;
        curNode = curNode->curLevel[ch - 'a'];
        if(nullptr == curNode) {
            cout << "a???" << endl;
            return ;
        }
        
        // cout << "start : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
        // we check the tmpRes directly using the trie
        // if(tree->inTrie(tmpRes) && 0 == hash.count(tmpRes)) {
        //     res.emplace_back(tmpRes);
        //     hash.insert(tmpRes);
        //     if(tree->endWith(tmpRes)) {
        //         tmpRes.pop_back();
        //         return;
        //     }
        // }
        if(nullptr != curNode && curNode->isEnd == true && 0 == hash.count(tmpRes)) {
            // cout << "find! >>>>> " << tmpRes << endl;
            res.emplace_back(tmpRes);
            hash.insert(tmpRes);
            if(!curNode->hasNext) {
                tmpRes.pop_back();
                return;
            }
        }

        // cout << "current[i, j] : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
        exploredFlag[i][j] = true;
        if(nullptr != curNode) {
            // not null
            for(int mvIdx = 0; mvIdx < 4; ++mvIdx) {
                int nextX = i + deltaX[mvIdx];
                int nextY = j + deltaY[mvIdx];
                // cout << "tryStart: [x, y] :" << nextX << " " << nextY << endl;;
                if( nextX < board.size() && nextX >= 0 && nextY < board[0].size() && nextY >= 0 && \
                    ! exploredFlag[nextX][nextY]) {
                    backTrack(nextX, nextY, board, tmpRes, res, curNode,
                        deltaX, deltaY, exploredFlag, hash
                    );
                }
                // cout << "tryFinish: [x, y] :" << nextX << " " << nextY << endl;;
            }
        }
        exploredFlag[i][j] = false;
        tmpRes.pop_back();
    }

    // OLD WAY TO DO, will exceed the time limitation
    // void backTrack(int i, int j, vector<vector<char>>& board, string& tmpRes, vector<string>& res, unique_ptr<Trie>& tree, 
    // const int* deltaX, const int* deltaY,
    // vector<vector<bool>>& exploredFlag,
    // unordered_set<string>& hash) {

    //     // start from i, j
    //     tmpRes.push_back(board[i][j]);
        
    //     // cout << "start : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
    //     if(tree->inTrie(tmpRes) && 0 == hash.count(tmpRes)) {
    //         res.emplace_back(tmpRes);
    //         hash.insert(tmpRes);
    //         if(tree->endWith(tmpRes)) {
    //             tmpRes.pop_back();
    //             return;
    //         }
    //     }


    //     // cout << "current[i, j] : in " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
    //     exploredFlag[i][j] = true;
    //     if(tree->startWith(tmpRes)) {
    //         for(int mvIdx = 0; mvIdx < 4; ++mvIdx) {
    //             int nextX = i + deltaX[mvIdx];
    //             int nextY = j + deltaY[mvIdx];
    //             if( nextX < board.size() && \
    //                 nextX >= 0 && \
    //                 nextY < board[0].size() && \
    //                 nextY >= 0 && \
    //                 ! exploredFlag[nextX][nextY]) {
    //                 backTrack(nextX, nextY, board, tmpRes, res, tree,
    //                     deltaX, deltaY, exploredFlag, hash
    //                 );
    //             }
    //             // cout << "tryFinish: [x, y] :" << nextX << " " << nextY << endl;;
    //         }
    //     }
    //     exploredFlag[i][j] = false;
    //     tmpRes.pop_back();
    //     // cout << "current[i, j] : exit " << i << "->" << j << " " << board[i][j] << "with tmpRes : " << tmpRes << endl;
    // }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204

0336. 回文对

1 题目

https://leetcode-cn.com/problems/palindrome-pairs/

2 解题思路

  • 1 参考官方解答：https://leetcode-cn.com/problems/palindrome-pairs/solution/hui-wen-dui-by-leetcode-solution/
class Solution {
public:
    class Trie {
    public:
        vector<Trie*> curLevel;
        bool isEnd = false;
        int wordIdx = -1;
        Trie() : curLevel(26), wordIdx(-1) {

        }
        void insert(string& word, int idx) {
            Trie* curNode = this;
            for(auto c : word) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    curNode->curLevel[c] = new Trie();
                }
                curNode = curNode->curLevel[c];
            }
            curNode->isEnd = true;
            curNode->wordIdx = idx;
        }
        
        int inTrie(string word) {
            Trie* curNode = this;
            for(auto c : word) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    return -1;
                }
                curNode = curNode->curLevel[c];
            }
            return curNode->wordIdx;
        }

        int inTrie(string& word, int left, int right) {
            Trie* curNode = this;
            for(int i = right; i >= left; --i) {
                char c = word[i] - 'a';
                if(nullptr == curNode->curLevel[c]) {
                    return -1;
                }
                curNode = curNode->curLevel[c];
            }
            return curNode->wordIdx;
        }
    };
 
    vector<vector<int>> palindromePairs(vector<string>& words) {
        // travel all prefix and subfix of a word,
        // find the palindrome and check the existence in the words of
        // reverse of the other part
        Trie* tree = new Trie();
        // Trie* treeReverse = new Trie();
        unordered_map<string, int> strToIdx;
        // int idx = 0;
        // for(auto word : words) {
        //     tree->insert(word);
        //     strToIdx[word] = idx++;
        // }
        
        // int ans = 0;
        // vector<vector<int>> res = {};
        // for(auto word : words) {
        //     deque<string> prefix; 
        //     deque<string> subfix;
        //     int n = word.size();
        //     for(int st = 0; st <= n; ++st) {
        //         string pre = word.substr(0, st);
        //         string sub = word.substr(st);
        //         // cout << "p/s : " << pre << " / " << sub << endl;
        //         if(checkPalindrome(pre)) {
        //             reverse(sub.begin(), sub.end());
        //             if(tree->inTrie(sub)) {
        //                 vector<int> resItem = {strToIdx[sub], strToIdx[word]};
        //                 if(resItem[1] != resItem[0]) {
        //                     // cout << "push: " << word + sub << endl;
        //                     res.emplace_back(resItem);
        //                 }
        //             }
        //         }
        //         if(checkPalindrome(sub) && pre.size() != n) {
        //             reverse(pre.begin(), pre.end());
        //             if(tree->inTrie(pre)) {
        //                 vector<int> resItem = {strToIdx[word], strToIdx[pre]};
        //                 if(resItem[1] != resItem[0]) {
        //                     // cout << "push: " << pre + word << endl;
        //                     res.emplace_back(vector<int>(resItem));
        //                 }
        //             }
        //         }
                
        //     }
        // }

        int idx = 0;
        for(auto word : words) {
            // tree->insert(word, idx);
            // reverse(word.begin(), word.end());
            tree->insert(word, idx);
            ++idx;
        }
        int tmp = 0;
        
        int ans = 0;
        vector<vector<int>> res = {};

        int curWordIdx = 0;
        for(auto word : words) {
            int n = word.size();
            for(int st = 0; st <= n; ++st) {
                string pre = word.substr(0, st);
                string sub = word.substr(st);
                // cout << "p/s : " << pre << " / " << sub << " curWordIdx : " << curWordIdx << endl;
                // if(checkPalindrome(pre)) {
                if(0 != st && checkPalindrome(word, 0, st-1)) {
                    // reverse(sub.begin(), sub.end());
                    int subIdx = tree->inTrie(word, st, n-1);
                    // cout << "subIdx = " << sub << "with idx = " << subIdx << endl;
                    if(subIdx != -1 && curWordIdx != subIdx) {
                        // cout << "curWordIdx / subIdx" << curWordIdx << "/" << subIdx << endl;
                        // cout << "push: " <<  sub << "+" << word << endl;
                        res.emplace_back(vector<int>({subIdx, curWordIdx}));
                    }
                }
                if(checkPalindrome(word, st, n-1)) {
                    // reverse(pre.begin(), pre.end());
                    int preIdx = tree->inTrie(word, 0, st-1);
                    if(preIdx != -1 && preIdx != curWordIdx) {
                        // cout << "curWordIdx / preIdx" << curWordIdx << "/" << preIdx << endl;
                        // cout << "push: " << pre << "+" + word << endl;
                        res.emplace_back(vector<int>({curWordIdx, preIdx}));
                    }
                }
                
            }
            ++curWordIdx;
        }
        return res;
    }
        // for (int i = 0; i < n; i++) {
        //     int m = words[i].size();
        //     for (int j = 0; j <= m; j++) {
        //         if (isPalindrome(words[i], j, m - 1)) {
        //             int left_id = findWord(words[i], 0, j - 1);
        //             if (left_id != -1 && left_id != i) {
        //                 ret.push_back({i, left_id});
        //             }
        //         }
        //         if (j && isPalindrome(words[i], 0, j - 1)) {
        //             int right_id = findWord(words[i], j, m - 1);
        //             if (right_id != -1 && right_id != i) {
        //                 ret.push_back({right_id, i});
        //             }
        //         }
        //     }
        // }

    bool checkPalindrome(string& s, int left, int right) {
        int len = right - left + 1;
        for(int i = 0; i < len / 2; ++i) {
            if(s[left + i] != s[right - i]) {
                return false;
            }
        }
        return true;
    }


    // bool checkPalindrome(string& s) {
    //     int n = s.size();
    //     for(int i = 0; i < n / 2; ++i) {
    //         if(s[i] != s[n - i - 1]) {
    //             return false;
    //         }
    //     }
    //     return true;
    // }
};


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180

3 使用hash表来查前后缀

class Solution {
public:
    class Trie {
    public:
        vector<Trie*> curLevel;
        bool isEnd = false;
        int wordIdx = -1;
        Trie() : curLevel(26), wordIdx(-1) {

        }
        void insert(string& word, int idx) {
            Trie* curNode = this;
            for(auto c : word) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    curNode->curLevel[c] = new Trie();
                }
                curNode = curNode->curLevel[c];
            }
            curNode->isEnd = true;
            curNode->wordIdx = idx;
        }
        
        int inTrie(string word) {
            Trie* curNode = this;
            for(auto c : word) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    return -1;
                }
                curNode = curNode->curLevel[c];
            }
            return curNode->wordIdx;
        }

        int inTrie(string& word, int left, int right) {
            Trie* curNode = this;
            for(int i = right; i >= left; --i) {
                char c = word[i] - 'a';
                if(nullptr == curNode->curLevel[c]) {
                    return -1;
                }
                curNode = curNode->curLevel[c];
            }
            return curNode->wordIdx;
        }
    };
 
    vector<string> wordReverse;
    unordered_map<string, int> strToIdx;

    int findWord(string& s, int left, int right) {
        string tmp = s.substr(left, right - left + 1);
        auto it = strToIdx.find(tmp);
        int res = it == strToIdx.end() ? -1 : it->second;
        // cout << "finding: " << tmp << " with ans = " << res << endl;
        return res;
    }
    

    vector<vector<int>> palindromePairs(vector<string>& words) {
        // travel all prefix and subfix of a word,
        // find the palindrome and check the existence in the words of
        // reverse of the other part
        int idx = 0;
        for(auto word : words) {
            reverse(word.begin(), word.end());
            wordReverse.emplace_back(word);
            strToIdx[word] = idx;
            ++idx;
        }

        vector<vector<int>> res = {};

        int curWordIdx = 0;
        for(auto word : words) {
            int n = word.size();
            for(int st = 0; st <= n; ++st) {
                // cout << "p/s : " << " / " << " curWordIdx : " << curWordIdx << endl;
                if(0 != st && checkPalindrome(word, 0, st-1)) {
                    int subIdx = findWord(word, st, n-1);
                    // cout << "subIdx = " << subIdx << endl;
                    if(subIdx != -1 && curWordIdx != subIdx) {
                        res.emplace_back(vector<int>({subIdx, curWordIdx}));
                    }
                }
                if(checkPalindrome(word, st, n-1)) {
                    int preIdx = findWord(word, 0, st-1);
                    if(preIdx != -1 && preIdx != curWordIdx) {
                        res.emplace_back(vector<int>({curWordIdx, preIdx}));
                    }
                }
                
            }
            ++curWordIdx;
        }
        return res;
    }


    bool checkPalindrome(string& s, int left, int right) {
        int len = right - left + 1;
        for(int i = 0; i < len / 2; ++i) {
            if(s[left + i] != s[right - i]) {
                return false;
            }
        }
        return true;
    }

};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111

0140. 单词拆分 II

1 题目

https://leetcode-cn.com/problems/word-break-ii/

2 解题思路

  • 1 首先确定搜索思路：
    • 1.1 很显然这个问题的解答思路不会随着问题规模的减小而改变，于是采用递归/回溯方案
    • 1.2 由于需要确认当前子问题处于什么位置，于是采用回溯
    • 1.3 回溯方法
      • 1.3.1 每次在头部尝试字符串headWord，直到找到一个在字典里面的headWord
      • 1.3.2 将原来字符串去掉headWord，然后递归到下一层
      • 1.3.3 当前的headWord的所有可能尝试完毕，则回溯到尝试headWord之前，然后去尝试下一个headWord
    • 1.4 以上可以看出回溯和递归的区别，递归不带有当前搜索状态，而回溯需要维持搜索状态
  • 2 有了大体思路，那么如何解决: 找到一个在字典里面的headWord?
    • 2.1 采用字典前缀树即可快速获得该字符串是否在字典树里面，复杂度为O(m)，m为字典树中的
class Solution {
public:
    class Trie {
    public:
        vector<Trie*> curLevel;
        bool isEnd = false;

        Trie() : curLevel(26){}

        void insert(string word ) {
            Trie* curNode = this;
            for(char c : word) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    curNode->curLevel[c] = new Trie();
                }
                curNode = curNode->curLevel[c];
            }
            curNode->isEnd = true;
        }

        bool inTrie(string word) {
            Trie* curNode = this;
            for(char c : word) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    return false;
                }
                curNode = curNode->curLevel[c];
            }
            return curNode->isEnd;
        }

        bool startWith(string word) {
            Trie* curNode = this;
            for(char c : word) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    return false;
                }
                curNode = curNode->curLevel[c];
            }
            return true;
        }
    };

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        // implement a trie to sort the word Dict
        Trie* tree = new Solution::Trie();
        for(string s : wordDict) {
            tree->insert(s);
        }

        vector<string> tmpRes;
        vector<vector<string>> res;
        backTrack(s, tmpRes, res, tree);

        vector<string> finalRes;
        for(auto& strVec : res) {
            string resItem = "";
            for(auto& str : strVec) {
                resItem += (str + " ");
            }
            finalRes.emplace_back(resItem.substr(0, resItem.size() - 1));
        }
        return finalRes;
    }

    void backTrack(string s, vector<string> tmpRes, vector<vector<string>>& res, Trie* trie) {
        if(0 == s.size()) {
            res.emplace_back(tmpRes);
        }
        // try every possibility
        for(int i = 0; i < s.size(); ++i) {
            string headWord = s.substr(0, i + 1);
            tmpRes.emplace_back(headWord);
            // cout << "head -> " << headWord << endl;
            if(trie->inTrie(headWord)) {
                // cout << "in it!" << endl;
                backTrack(s.substr(i + 1), tmpRes, res, trie);
            }
            tmpRes.pop_back();
        }
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85

0472. 连接词

1 题目

https://leetcode-cn.com/problems/concatenated-words/

2 解题思路

  • 1 首先很容易想到一点：
    • 1.1 由于需要快速定位一个单词是否在字典里，则采用字典树获取该信息
    • 1.2 对于一个单词，我们对于每个isEnd(也就是搜索前缀对应的单词在字典里)的位置，都从下一个字符从新开始在字典中匹配，然后每个isEnd位置后面的字符，需要继续匹配，eg：[cat, cats, catsdog, dog]，对于catsdog，从sdog和dog分别重新匹配
    • 1.3 对于一个单词，它的构成成分比他小，于是将字符串排序，一边插入，一边找
  • 2 通过后缀记忆剪枝dfs, eg: 对于[“a”, “aa”, “aaaa”, “aaaakaa”]中的aaaakaa，运行代码会有如下日志：
    • 因为在第一次 a,a,a,a,k的时候记录了k位置往后的后缀无法成功匹配
    • 那么对于后面的 aa,a,a,k以及aaa,a,k等等搜索都会直接跳过k后缀的匹配
when checking : aaaakaa the sufix start from pos : 4 has been validated to be failure!
when checking : aaaakaa the sufix start from pos : 3 has been validated to be failure!
when checking : aaaakaa the sufix start from pos : 2 has been validated to be failure!
when checking : aaaakaa the sufix start from pos : 4 has been validated to be failure!

  • 1
  • 2
  • 3
  • 4
class Solution {
public:
    class Trie{
    public: 
        vector<Trie*> curLevel;
        bool isEnd = false;
        // bool hasNext = false;

        Trie() : curLevel(26) {

        }

        void insert(string& s, int idx) {
            // cout << "inserting : " << s << endl;
            Trie* curNode = this;
            for(auto c : s) {
                c -= 'a';
                if(nullptr == curNode->curLevel[c]) {
                    curNode->curLevel[c] = new Trie();
                }

                curNode = curNode->curLevel[c];
                // curNode->hasNext = true;
            }
            curNode->isEnd = true;
        }
    };

    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        int n = words.size();
        Trie* tree = new Trie();
        
        // build trie
        int idx = 0;

        sort(words.begin(), words.end(), [](string& a, string& b){
            return a.size() < b.size();
        });

        vector<string> ans;


        for(auto w : words) {
            // cout << "-------checking " << w << endl;
            // bool ableToConnect = false;
            // findMaxConnectedCnt(w, 0, tree, 0, ableToConnect);
            // if(ableToConnect ) {
            //     ans.emplace_back(w);
            // }
            vector<bool> trap(w.size(), false);
            if(dfsToCheck(w, 0, tree, 0, trap)) {
                ans.emplace_back(w);
            }
            tree->insert(words[idx], idx);
            ++idx;
        }

        return ans;
    }

    // here we search all the possible ways, but we only need one possible way, so we need return early
    void findMaxConnectedCnt(string& s, int pos, Trie* root, int curCnt, bool& ableToConnect) {

        if(s.size() == pos) {
            if(curCnt >= 2) {
                ableToConnect = true;
            }
            // cout << "<<<<<< finish one!"  << endl;
            return ;
        }
        
        int curPos = pos;
        Trie* curNode = root;
        while(curPos < s.size()) { // serach all prefix
            int ch = s[curPos] - 'a';
            if(nullptr != curNode->curLevel[ch]) {
                if(curNode->curLevel[ch]->isEnd) {
                    // cout << ">>>>> curPos: " << curPos << " char is " << s[curPos] << " dive with curCnt: " << curCnt << endl;
                    // using this or next end
                    findMaxConnectedCnt(s, curPos + 1, root, curCnt + 1, ableToConnect);
                }
            } else {
                return;
            }
            // cout << "curPos: " << curPos << " char is " << s[curPos] << " with curCnt: " << curCnt << endl;
            curNode = curNode->curLevel[ch];
            ++curPos;
        }
    }

    bool dfsToCheck(string& s, int pos, Trie* root, int curCnt, vector<bool>& trap) {

        if(s.size() == pos) {
            return curCnt >= 2;
        }

        if(trap[pos]) {
            cout << "when checking : " << s << " the sufix start from pos : " << pos << " has been validated to be failure!" << endl;
            return false;
        }
        
        int curPos = pos;
        Trie* curNode = root;
        while(curPos < s.size()) { // serach all prefix
            int ch = s[curPos] - 'a';
            if(nullptr != curNode) {
                if(nullptr != curNode->curLevel[ch]) {
                    if(curNode->curLevel[ch]->isEnd) {
                        // cout << ">>>>> curPos: " << curPos << " char is " << s[curPos] << " dive with curCnt: " << curCnt << endl;
                        // using this or next end
                        if(dfsToCheck(s, curPos + 1, root, curCnt + 1, trap)) {
                            return true;
                        }
                    }
                }
            } else {
                break;
            }
            
            // cout << "curPos: " << curPos << " char is " << s[curPos] << " with curCnt: " << curCnt << endl;
            curNode = curNode->curLevel[ch];
            ++curPos;
        }
        
        trap[pos] = true;
        return false;
    }

};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129

0745WordFilter 前缀和后缀搜索

1 题目

https://leetcode-cn.com/problems/prefix-and-suffix-search/

2 解题思路

  • 1 构建后缀拼接前缀树
    1.1 参考解释即可：

For a word like “test”, consider “#test”, “t#test”, “st#test”, “est#test”, “test#test”. Then if we have a query like prefix = “te”, suffix = “t”, we can find it by searching for something we’ve inserted starting with “t#te”.

class WordFilter {
public:
    // containning suffix
    class Trie {
    public:
        vector<Trie*> curLevel;
        int idx = -1;
        Trie() : curLevel(27) {}

        void insert(string& word, int idx, int left, int right) {
            Trie* curNode = this;
            for(int i = left; i < right; ++i) {
                char c = word[i];
                c = (c == '#' ? 26 : c - 'a');
                if(nullptr == curNode->curLevel[c]) {
                    curNode->curLevel[c] = new Trie();
                }
                curNode = curNode->curLevel[c];
                curNode->idx = idx;
            }
            curNode->idx = idx;
        }

        int startWith(string& word) {
            Trie* curNode = this;
            int lastIdx = -1;
            for(auto c : word) {
                // cout << "checking char: " << c << endl;
                c = (c == '#' ? 26 : c - 'a');
                if(nullptr == curNode->curLevel[c]) {
                    return -1;
                }
                curNode = curNode->curLevel[c];
            }
            return curNode->idx;
        }
    };

    public:
        Trie* tree;


    WordFilter(vector<string>& words) {
        tree = new Trie();
        for(int wIdx = 0; wIdx < words.size(); ++wIdx) {
            int n = words[wIdx].size();
            string word = words[wIdx] + "#" + words[wIdx];
            for(int j = 0; j <= n - 1; ++j) {
                // string tmp = word.substr(j);
                // overwrite those who start with a same suffix and prefix
                // cout <<"insert : " << tmp << endl;
                tree->insert(word, wIdx, j, 2*n +1);
            }
        }
    }
    
    int f(string prefix, string suffix) {
        int ans = -1;
        string tmp = suffix + "#" + prefix;
        // cout << "target >> " << tmp << endl;
        return tree->startWith(tmp);

    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

1032. 字符流 StreamChecke

1 题目

https://leetcode-cn.com/problems/stream-of-characters/

2 解题思路

  • 1 倒序建立搜索树即可，因为可以观察到，总是从字符流的倒序开始查询
class StreamChecker {
public:
    class Trie{
    public:
        vector<Trie*> curLevel;
        bool isEnd = false;

        Trie() : curLevel(26) {}

        void insert(string& word) {
            Trie* curNode = this;
            int n = word.size();
            for(int i = n-1; i >= 0; --i) {
                char c = word[i] - 'a';
                if(nullptr == curNode->curLevel[c]) {
                    curNode->curLevel[c] = new Trie();
                }
                curNode = curNode->curLevel[c];
            }
            curNode->isEnd = true;
        }

        bool inTrie(string& word) {
            Trie* curNode = this;
            int n = word.size();
            for(int i = n-1; i >= 0; --i) {
                char c = word[i] - 'a';
                if(nullptr == curNode->curLevel[c]) {
                    return false;
                }
                if(curNode->curLevel[c]->isEnd) {
                    return true;
                }
                curNode = curNode->curLevel[c];
            }
            return curNode->isEnd;
        }

    };

    Trie* root;
    string curStr;

    StreamChecker(vector<string>& words) {
        root = new Trie();
        for(auto& w : words) {
            root->insert(w);
        }

        curStr = "";
    }
    
    bool query(char letter) {
        curStr += letter;
        return root->inTrie(curStr);
    }
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 *

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号