数据结构丨前缀树

数据结构丨前缀树前缀树简介什么是前缀树?是`N叉树存储字符串字符串前缀原始字符串通往该子节点路径上所有的字符`组成的。下面是前缀树的一个例子:在上图示例中,我们在节点中标记的值是该节点对应表示的字符串。例如,我们从根节点开始,选择第二条路径'b',然后选择它的第一个子节点&#3

大家好,欢迎来到IT知识分享网。

前缀树简介

什么是前缀树?

前缀树N叉树的一种特殊形式。通常来说,一个前缀树是用来存储字符串的。前缀树的每一个节点代表一个字符串前缀)。每一个节点会有多个子节点,通往不同子节点的路径上有着不同的字符。子节点代表的字符串是由节点本身的原始字符串,以及通往该子节点路径上所有的字符组成的。

下面是前缀树的一个例子:

img

在上图示例中,我们在节点中标记的值是该节点对应表示的字符串。例如,我们从根节点开始,选择第二条路径 ‘b’,然后选择它的第一个子节点 ‘a’,接下来继续选择子节点 ‘d’,我们最终会到达叶节点 “bad”。节点的值是由从根节点开始,与其经过的路径中的字符按顺序形成的。

值得注意的是,根节点表示空字符串

前缀树的一个重要的特性是,节点所有的后代都与该节点相关的字符串有着共同的前缀。这就是前缀树名称的由来。

我们再来看这个例子。例如,以节点 “b” 为根的子树中的节点表示的字符串,都具有共同的前缀 “b”。反之亦然,具有公共前缀 “b” 的字符串,全部位于以 “b” 为根的子树中,并且具有不同前缀的字符串来自不同的分支。

前缀树有着广泛的应用,例如自动补全,拼写检查等等。我们将在后面的章节中介绍实际应用场景。

如何表示一个前缀树?

在前面的文章中,我们介绍了前缀树的概念。在这篇文章中,我们将讨论如何用代码表示这个数据结构。

在阅读一下内容前,请简要回顾N叉树的节点结构。

前缀树的特别之处在于字符和子节点之间的对应关系。有许多不同的表示前缀树节点的方法,这里我们只介绍其中的两种方法。

方法一 – 数组

第一种方法是用数组存储子节点。

例如,如果我们只存储含有字母 az 的字符串,我们可以在每个节点中声明一个大小为26的数组来存储其子节点。对于特定字符 c,我们可以使用 c - 'a' 作为索引来查找数组中相应的子节点。

// change this value to adapt to different cases
#define N 26

struct TrieNode {
    TrieNode* children[N];
    
    // you might need some extra values according to different cases
};

/** Usage:
 *  Initialization: TrieNode root = new TrieNode();
 *  Return a specific child node with char c: (root->children)[c - 'a']
 */

访问子节点十分快捷。访问一个特定的子节点比较容易,因为在大多数情况下,我们很容易将一个字符转换为索引。但并非所有的子节点都需要这样的操作,所以这可能会导致空间的浪费

方法二 – Map

第二种方法是使用 Hashmap 来存储子节点。

我们可以在每个节点中声明一个Hashmap。Hashmap的键是字符,值是相对应的子节点。

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    
    // you might need some extra values according to different cases
};

/** Usage:
 *  Initialization: TrieNode root = new TrieNode();
 *  Return a specific child node with char c: (root->children)[c]
 */

通过相应的字符来访问特定的子节点更为容易。但它可能比使用数组稍慢一些。但是,由于我们只存储我们需要的子节点,因此节省了空间。这个方法也更加灵活,因为我们不受到固定长度和固定范围的限制。

补充

我们已经提到过如何表示前缀树中的子节点。除此之外,我们也需要用到一些其他的值。

例如,我们知道,前缀树的每个节点表示一个字符串,但并不是所有由前缀树表示的字符串都是有意义的。如果我们只想在前缀树中存储单词,那么我们可能需要在每个节点中声明一个布尔值(Boolean)作为标志,来表明该节点所表示的字符串是否为一个单词。

基本操作

Insertion in Trie

我们已经在另一张卡片中讨论了 (如何在二叉搜索树中实现插入操作)。

提问:

你还记得如何在二叉搜索树中插入一个新的节点吗?

当我们在二叉搜索树中插入目标值时,在每个节点中,我们都需要根据 节点值目标值 之间的关系,来确定目标值需要去往哪个子节点。同样地,当我们向前缀树中插入一个目标值时,我们也需要根据插入的 目标值 来决定我们的路径。

更具体地说,如果我们在前缀树中插入一个字符串 S,我们要从根节点开始。 我们将根据 S[0](S中的第一个字符),选择一个子节点或添加一个新的子节点。然后到达第二个节点,并根据 S[1] 做出选择。 再到第三个节点,以此类推。 最后,我们依次遍历 S 中的所有字符并到达末尾。 末端节点将是表示字符串 S 的节点。

下面是一个例子:

search

我们来用伪代码总结一下以上策略:

1. Initialize: cur = root
2. for each char c in target string S:
3.      if cur does not have a child c:
4.          cur.children[c] = new Trie node
5.      cur = cur.children[c]
6. cur is the node which represents the string S

通常情况情况下,你需要自己构建前缀树。构建前缀树实际上就是多次调用插入函数。但请记住在插入字符串之前要 初始化根节点

Search in Trie

搜索前缀

正如我们在前缀树的简介中提到的,所有节点的后代都与该节点相对应字符串的有着共同前缀。因此,很容易搜索以特定前缀开头的任何单词。

同样地,我们可以根据给定的前缀沿着树形结构搜索下去。一旦我们找不到我们想要的子节点,搜索就以失败终止。否则,搜索成功。为了更具体地解释搜索的过程,我们提供了下列示例:

search2

我们来用伪代码总结一下以上策略:

1. Initialize: cur = root
2. for each char c in target string S:
3.      if cur does not have a child c:
4.          search fails
5.      cur = cur.children[c]
6. search successes

搜索单词

你可能还想知道如何搜索特定的单词,而不是前缀。我们可以将这个词作为前缀,并同样按照上述同样的方法进行搜索。

  1. 如果搜索失败,那么意味着没有单词以目标单词开头,那么目标单词绝对不会存在于前缀树中。
  2. 如果搜索成功,我们需要检查目标单词是否是前缀树中单词的前缀,或者它本身就是一个单词。为了进一步解决这个问题,你可能需要稍对节点的结构做出修改。

提示:往每个节点中加入布尔值可能会有效地帮助你解决这个问题。

实现Trie(前缀树)

实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

说明:

  • 你可以假设所有的输入都是由小写字母 a-z 构成的。
  • 保证所有输入均为非空字符串。

递归解法

#include <iostream>
#include <vector>
#include <map>

using namespace std;

/// Trie Recursive version
class Trie{

private:
    struct Node{
        map<char, int> next;
        bool end = false;
    };
    vector<Node> trie;

public:
    Trie(){
        trie.clear();
        trie.push_back(Node());
    }

    /** Inserts a word into the trie. */
    void insert(const string& word){
        insert(0, word, 0);
    }

    /** Returns if the word is in the trie. */
    bool search(const string& word){
        return search(0, word, 0);
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(const string& prefix) {
        return startsWith(0, prefix, 0);
    }

private:
    void insert(int treeID, const string& word, int index){

        if(index == word.size()) {
            trie[treeID].end = true;
            return;
        }

        if(trie[treeID].next.find(word[index]) == trie[treeID].next.end()){
            trie[treeID].next[word[index]] = trie.size();
            trie.push_back(Node());
        }

        insert(trie[treeID].next[word[index]], word, index + 1);
    }

    bool search(int treeID, const string& word, int index){

        if(index == word.size())
            return trie[treeID].end;

        if(trie[treeID].next.find(word[index]) == trie[treeID].next.end())
            return false;

        return search(trie[treeID].next[word[index]], word, index + 1);
    }

    bool startsWith(int treeID, const string& prefix, int index){

        if(index == prefix.size())
            return true;

        if(trie[treeID].next.find(prefix[index]) == trie[treeID].next.end())
            return false;

        return startsWith(trie[treeID].next[prefix[index]], prefix, index + 1);
    }
};


void printBool(bool res){
    cout << (res ? "True" : "False") << endl;
}

int main() {

    Trie trie1;
    trie1.insert("ab");
    printBool(trie1.search("a"));     // false
    printBool(trie1.startsWith("a")); // true;

    cout << endl;

    // ---

    Trie trie2;
    trie2.insert("a");
    printBool(trie2.search("a"));     // true
    printBool(trie2.startsWith("a")); // true;

    return 0;
}

非递归解法

#include <iostream>
#include <vector>
#include <map>

using namespace std;

/// Trie Recursive version
class Trie{

private:
    struct Node{
        map<char, int> next;
        bool end = false;
    };
    vector<Node> trie;
public: 
    Trie(){
        trie.clear();
        trie.push_back(Node());
    }

    void insert(const string& word){
        int treeID = 0;
        for(char c: word){
            //若未找到该节点
            if(trie[treeID].next.find(c) == trie[treeID].next.end()){
                trie[treeID].next[c] = trie.size();
                trie.push_back(Node());
            }
            treeID = trie[treeID].next[c];
        }
        trie[treeID].end = true;
    }
    bool search(const string& word){
        int treeID = 0;
        for(char c: word){
            if(trie[treeID].next.find(c)==trie[treeID].next.end())
                return false;
            treeID = trie[treeID].next[c];
        }
        return trie[treeID].end;
    }
    bool startsWith(const string& prefix){
        int treeID = 0;
        for(char c: prefix){
            if(trie[treeID].next.find(c)==trie[treeID].next.end())
                return false;
            treeID = trie[treeID].next[c];
        }
        return true;
    }
};

void printBool(bool res){
    cout << (res? "True" : "False") << endl;
}

int main() {

    Trie trie1;
    trie1.insert("ab");
    printBool(trie1.search("a"));     // false
    printBool(trie1.startsWith("a")); // true;

    cout << endl;

    // ---

    Trie trie2;
    trie2.insert("a");
    printBool(trie2.search("a"));     // true
    printBool(trie2.startsWith("a")); // true;

    return 0;
}

实际应用I

Map Sum Pairs

实现一个 MapSum 类里的两个方法,insertsum

对于方法 insert,你将得到一对(字符串,整数)的键值对。字符串表示键,整数表示值。如果键已经存在,那么原来的键值对将被替代成新的键值对。

对于方法 sum,你将得到一个表示前缀的字符串,你需要返回所有以该前缀开头的键的值的总和。

示例 1:

输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5

参考数据结构丨前缀树

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

//这道题让我们实现一个MapSum类,里面有两个方法,insert和sum,其中inser就是插入一个键值对,而sum方法比较特别,是在找一个前缀,需要将所有有此前缀的单词的值累加起来返回。看到这种玩前缀的题,照理来说是要用前缀树来做的。但是博主一般想偷懒,不想新写一个结构或类,于是就使用map来代替前缀树啦。博主开始想到的方法是建立前缀和一个pair之间的映射,这里的pair的第一个值表示该词的值,第二个值表示将该词作为前缀的所有词的累加值,那么我们的sum函数就异常的简单了,直接将pair中的两个值相加即可。关键就是要在insert中把数据结构建好,构建的方法也不难,首先我们suppose原本这个key是有值的,我们更新的时候只需要加上它的差值即可,就算key不存在默认就是0,算差值也没问题。然后我们将first值更新为val,然后就是遍历其所有的前缀了,给每个前缀的second都加上diff即可,参见代码如下:
class MapSum{
private: 
    unordered_map<string, pair<int, int>> m;
public:
    MapSum(){}

    void insert(string key, int val){
        //diff的作用防止重复插入
        int diff = val - m[key].first, n = key.size();
        m[key].first = val;
        for(int i=n-1; i>0; --i)
            m[key.substr(0, i)].second += diff;
    }
    int sum(string prefix){
        return m[prefix].first + m[prefix].second;
    }
};

//下面这种方法是论坛上投票最高的方法,感觉很叼,用的是带排序的map,insert就是把单词加入map。在map里会按照字母顺序自动排序,然后在sum函数里,我们根据prefix来用二分查找快速定位到第一个不小于prefix的位置,然后向后遍历,向后遍历的都是以prefix为前缀的单词,如果我们发现某个单词不是以prefix为前缀了,直接break;否则就累加其val值,参见代码如下:
class MapSum{
private:
    map<string, int> m;
public:
    MapSum(){}
    void insert(string key, int val){
        m[key] = val;
    }
    int sum(string prefix){
        int res = 0, n = prefix.size();
        for(auto it = m.lower_bound(prefix); it != m.end(); ++it){
            if(it->first.substr(0, n) != prefix) break;
            res += it->second;
        }
        return res;
    }
};

单词替换

在英语中,我们有一个叫做 词根(root)的概念,它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 other(其他),可以形成新的单词 another(另一个)。

现在,给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词词根替换掉。如果继承词有许多可以形成它的词根,则用最短的词根替换它。

你需要输出替换之后的句子。

示例 1:

输入: dict(词典) = ["cat", "bat", "rat"]
sentence(句子) = "the cattle was rattled by the battery"
输出: "the cat was rat by the bat"

注:

  1. 输入只包含小写字母。
  2. 1 <= 字典单词数 <=1000
  3. 1 <= 句中词语数 <= 1000
  4. 1 <= 词根长度 <= 100
  5. 1 <= 句中词语长度 <= 1000

参考https://www.cnblogs.com/grandyang/p/7423420.html

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

//这道题最好的解法其实是用前缀树(Trie / Prefix Tree)来做,关于前缀树使用之前有一道很好的入门题Implement Trie (Prefix Tree)。了解了前缀树的原理机制,那么我们就可以发现这道题其实很适合前缀树的特点。我们要做的就是把所有的前缀都放到前缀树里面,而且在前缀的最后一个结点的地方将标示isWord设为true,表示从根节点到当前结点是一个前缀,然后我们在遍历单词中的每一个字母,我们都在前缀树查找,如果当前字母对应的结点的表示isWord是true,我们就返回这个前缀,如果当前字母对应的结点在前缀树中不存在,我们就返回原单词,这样就能完美的解决问题了。所以啊,以后遇到了有关前缀或者类似的问题,一定不要忘了前缀树这个神器哟~
class Solution{
public: 
    class TrieNode{
        public: 
        bool isWord;
        TrieNode *child[26];
        // TrieNode(){};
        TrieNode(){
            isWord = false;
            for(auto &a : child) a = NULL;
        };
    };
    string replaceWords(vector<string>& dict, string sentence){
        string res = "", t="";
        istringstream is(sentence);
        TrieNode* root = new TrieNode();
        for(string word: dict){
            insert(root, word);
        }
        while(is >> t){
            if(!res.empty()) res += " ";
            res += findPrefix(root, t);
        }
        return res;
    }
    void insert(TrieNode* node, string word){
        for(char c: word){
            if(!node->child[c-'a']) node->child[c-'a'] = new TrieNode();
            node = node->child[c-'a'];
        }
        node->isWord = true;
    }
    string findPrefix(TrieNode* node, string word){
        string cur = "";
        for(char c: word){
            if(!node->child[c-'a']) break;
            cur.push_back(c);
            node = node->child[c - 'a'];
            if(node->isWord) return cur;
        }
        return word;
    }
};

添加与搜索单词 – 数据结构设计

设计一个支持以下两种操作的数据结构:

void addWord(word)
bool search(word)

search(word) 可以搜索文字或正则表达式字符串,字符串只包含字母 .a-z. 可以表示任何一个字母。

示例:

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

说明:

你可以假设所有单词都是由小写字母 a-z 组成的。

#include <iostream>
#include <vector>
using namespace std;

class WordDictionary{
private:
    struct TrieNode{
        bool isWord;
        vector<TrieNode*> children;
        TrieNode(): isWord(false), children(26, nullptr){}
        ~TrieNode(){
            for(TrieNode* child: children)
                if(child) delete child;
        }
    };
    TrieNode* trieRoot;
    bool myFind(string &str, TrieNode* nowPtr, int nowIndex){
        int strSize = str.size();
        if(nowPtr == NULL){
            return false;
        }
        if(nowIndex >= strSize){
            if(nowPtr->isWord){
                return true;
            }
            return false;
        }
        else if(str[nowIndex] != '.'){
            if(nowPtr->children[str[nowIndex] - 'a'] != NULL){
                return myFind(str, nowPtr->children[str[nowIndex] - 'a'], nowIndex+1);
            }
            return false;
        }
        else{
            for(int i=0; i<26; ++i){
                if(nowPtr->children[i] != NULL && myFind(str, nowPtr->children[i], nowIndex+1 )){
                    return true;
                }
            }
        }
        return false;
    }
public: 
    WordDictionary(){
        trieRoot = new TrieNode();
    }
    void addWord(string word){
        TrieNode * ptr = trieRoot;
        for(auto ch : word){
            if(ptr->children[ch - 'a'] == NULL){
                ptr->children[ch - 'a'] = new TrieNode();
            }
            ptr = ptr->children[ch - 'a'];
        }
        ptr->isWord = true;
    }
    bool search(string word){
        return myFind(word, trieRoot, 0);
    }
};

实际应用II

数组中两个树的最大异或值

给定一个非空数组,数组中元素为 a0, a1, a2, … , an-1,其中 0 ≤ ai < 2^31 。

找到 ai 和aj 最大的异或 (XOR) 运算结果,其中0 ≤ i, j < n

你能在O(n)的时间解决这个问题吗?

示例:

输入: [3, 10, 5, 25, 2, 8]

输出: 28

解释: 最大的结果是 5 ^ 25 = 28.
//https://blog.csdn.net/weijiechenlun133/article/details/70135937
class SolutionA
{
public:
    int findMaximumXOR(vector<int> &nums)
    {
        if (nums.size() < 2)    return 0;
        int maxNum = 0;
        int flag = 0;
        for(int i = 31; i>=0; --i){
            set<int> hash;

            flag |= (1 << i);
            for(int x:nums)
                hash.insert(flag & x);

            int tmp = maxNum | (1<<i);
            for(int x:hash){
                if(hash.find(x^tmp)!=hash.end()){
                    maxNum = tmp;
                    break;
                }
            }
        }
        return maxNum;
    }
};

struct Node{
    Node* next[2];
    Node(){
        next[0] = nullptr;
        next[1] = nullptr;
    }
};
class SolutionB{
public:
    void buildTrieTree(Node* root, int x){
        for(int i = 31; i>=0; --i){
            int flag = (x & (1<<i) )? 1:0;
            if(root->next[flag] == nullptr){
                root->next[flag] = new Node();
            }
            root = root->next[flag];
        }
    }
    int findMaxXorInTire(Node* root, int x){
        int result = 0;
        for(int i = 31; i>=0; --i){
            int flag = (x & (1<<i) )? 0:1;
            if(root->next[flag] != nullptr){
                result |= (1<<i);   //result = result | (1<<i)
                root = root->next[flag];
            }
            else
                root = root->next[1-flag];
        }
        return result;
    }
    int findMaximumXOR(vector<int>& nums){
        if(nums.size()<2) return 0;
        Node head;
        for(int x : nums)
            buildTrieTree(&head, x);
        int maxNum = 0;
        for(int x: nums){
            int m = findMaxXorInTire(&head, x);
            maxNum = max(maxNum, m);
        }
        return maxNum;
    }
};

单词搜索II

给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例:

输入: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

输出: ["eat","oath"]

说明:
你可以假设所有输入都由小写字母 a-z 组成。

提示:

  • 你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯?
  • 如果当前单词不存在于所有单词的前缀中,则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作?散列表是否可行?为什么? 前缀树如何?如果你想学习如何实现一个基本的前缀树,请先查看这个问题: 实现Trie(前缀树)。

参考:https://blog.csdn.net/qq_41855420/article/details/88064909

#include <iostream>
#include <vector>

using namespace std;

//前缀树的程序表示
class TrieNode {
public:
	bool isWord;//当前节点为结尾是否是字符串
	vector<TrieNode*> children;
	TrieNode() : isWord(false), children(26, nullptr) {}
	~TrieNode() {
		for (TrieNode* child : children)
			if (child) delete child;
	}
};
class Solution {
private:
	TrieNode * trieRoot;//构建的单词前缀树
	//在树中插入一个单词的方法实现
	void addWord(string word) {
		TrieNode *ptr = trieRoot;//扫描这棵树,将word插入
		//将word的字符逐个插入
		for (auto ch : word) {
			if (ptr->children[ch - 'a'] == NULL) {
				ptr->children[ch - 'a'] = new TrieNode();
			}
			ptr = ptr->children[ch - 'a'];
		}
		ptr->isWord = true;//标记为单词
	}
public:
	int rowSize;//board的行数
	int colSize;//board的列数
	vector<vector<bool>> boardFlag;//标记board[row][col]是否已使用
	//以board[row][col]为中心点,四个方向进行尝试搜索
	void dfs(vector<vector<char>>& board, vector<string> &result, string &tempRes, TrieNode * nowRoot, int row, int col) {
		if (nowRoot == NULL) {
			return;
		}
		if (nowRoot->isWord) {//如果这个单词成功找到
			result.push_back(tempRes);//放入结果
			nowRoot->isWord = false;//将这个单词标记为公共后缀 防止重复
		}
		string tempResAdd;
		//上方测试
		//如果上方未出界,没有被使用,且nowRoot->children中存在相等的节点
		if (row - 1 >= 0 && !boardFlag[row - 1][col] && nowRoot->children[board[row - 1][col] - 'a'] != NULL) {
			boardFlag[row - 1][col] = true;//标记使用
			tempResAdd = tempRes + char(board[row - 1][col]);
			dfs(board, result, tempResAdd, nowRoot->children[board[row - 1][col] - 'a'], row - 1, col);
			boardFlag[row - 1][col] = false;//取消标记
		}
		//下方测试
		//如果下方未出界,没有被使用,且nowRoot->children中存在相等的节点
		if (row + 1 < rowSize && !boardFlag[row + 1][col] && nowRoot->children[board[row + 1][col] - 'a'] != NULL) {
			boardFlag[row + 1][col] = true;//标记使用
			tempResAdd = tempRes + char(board[row + 1][col]);
			dfs(board, result, tempResAdd, nowRoot->children[board[row + 1][col] - 'a'], row + 1, col);
			boardFlag[row + 1][col] = false;//取消标记
		}
		//左方测试
		//如果左方未出界,没有被使用,且nowRoot->children中存在相等的节点
		if (col - 1 >= 0 && !boardFlag[row][col - 1] && nowRoot->children[board[row][col - 1] - 'a'] != NULL) {
			boardFlag[row][col - 1] = true;//标记使用
			tempResAdd = tempRes + char(board[row][col - 1]);
			dfs(board, result, tempResAdd, nowRoot->children[board[row][col - 1] - 'a'], row, col - 1);
			boardFlag[row][col - 1] = false;//取消标记
		}
		//右方测试
		//如果右方未出界,没有被使用,且nowRoot->children中存在相等的节点
		if (col + 1 < colSize && !boardFlag[row][col + 1] && nowRoot->children[board[row][col + 1] - 'a'] != NULL) {
			boardFlag[row][col + 1] = true;//标记使用
			tempResAdd = tempRes + char(board[row][col + 1]);
			dfs(board, result, tempResAdd, nowRoot->children[board[row][col + 1] - 'a'], row, col + 1);
			boardFlag[row][col + 1] = false;//取消标记
		}
	}
	vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
		rowSize = board.size();
		if (rowSize == 0) {
			return {};
		}
		colSize = board[0].size();
		boardFlag = vector<vector<bool>>(rowSize, vector<bool>(colSize, false));//构建标记容器
		trieRoot = new TrieNode();//单词后缀树
        //将单词都放入前缀树中
		for (auto word : words) {
			addWord(word);
		}
		vector<string> result;//用于存储结果
		string tempRes;
		for (int row = 0; row < rowSize; ++row) {
			for (int col = 0; col < colSize; ++col) {
				if (trieRoot->children[board[row][col] - 'a'] != NULL) {//搜索
					tempRes = "";
					tempRes += char(board[row][col]);
					boardFlag[row][col] = true;//标记使用
					dfs(board, result, tempRes, trieRoot->children[board[row][col] - 'a'], row, col);
					boardFlag[row][col] = false;//取消使用
				}
			}
		}
		return result;
	}
};

回文对

给定一组唯一的单词, 找出所有不同 的索引对(i, j),使得列表中的两个单词, words[i] + words[j] ,可拼接成回文串。

示例 1:

输入: ["abcd","dcba","lls","s","sssll"]
输出: [[0,1],[1,0],[3,2],[2,4]] 
解释: 可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]

示例 2:

输入: ["bat","tab","cat"]
输出: [[0,1],[1,0]] 
解释: 可拼接成的回文串为 ["battab","tabbat"]

大多数解法都是基于hash表,看着很复杂,我找到一个可读性比较高的版本,之后还得拿出来温习。

#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <string>

using namespace std;

class Solution{
public: 
    bool isPalindrome(string& s, int start, int end){
        while(start < end)
            if(s[start++] != s[end--])
                return false;
            return true;
    }
    vector<vector<int>> palindromePairs(vector<string> words){
        vector<vector<int>> ans;
        unordered_map<string, int> dict;
        int len = words.size();
        for(int i=0; i<len; i++)
            dict[words[i]] = i;
        for(int i=0; i<len; i++){
            string cur = words[i];
            int clen = cur.size();
            for(int j=0; j<=clen; j++){
                //找后缀
                if(isPalindrome(cur, j, clen - 1)){
                    string suffix = cur.substr(0, j);
                    reverse(suffix.begin(), suffix.end());
                    if(dict.find(suffix)!=dict.end() && i!=dict[suffix])
                        ans.push_back({i, dict[suffix]});
                }
                //找前缀
                if(j>0 && isPalindrome(cur, 0, j-1)){
                    string prefix = cur.substr(j);
                    reverse(prefix.begin(), prefix.end());
                    if(dict.find(prefix) != dict.end() && i!=dict[prefix])
                        ans.push_back({dict[prefix], i});
                }
            }
        }
        return ans;
    }
};

int main(){
    vector<string> a = {"lls", "s", "sssll"};
    Solution s = Solution();
    vector<vector<int>> v =  s.palindromePairs(a);
};

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/30680.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信