数据结构丨前缀树

前缀树简介

什么是前缀树？

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

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

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

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

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

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

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

如何表示一个前缀树？

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

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

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

方法一 - 数组

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

例如，如果我们只存储含有字母 a 到 z 的字符串，我们可以在每个节点中声明一个大小为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 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 的节点。

下面是一个例子：

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

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

搜索单词

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

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

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

实现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 
#include 
#include 

using namespace std;

/// Trie Recursive version
class Trie{

private:
    struct Node{
        map next;
        bool end = false;
    };
    vector 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") <


非递归解法
#include 
#include 
#include 

using namespace std;

/// Trie Recursive version
class Trie{

private:
    struct Node{
        map next;
        bool end = false;
    };
    vector 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") <

实际应用I
Map Sum Pairs
实现一个 MapSum 类里的两个方法，insert 和 sum。
对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。
对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。
示例 1:
输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5

参考https://www.cnblogs.com/grandyang/p/7616525.html
#include 
#include 

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> 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 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 <= 字典单词数 <=1000
1 <=  句中词语数 <= 1000
1 <= 词根长度 <= 100
1 <= 句中词语长度 <= 1000

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

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& 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 
#include 
using namespace std;

class WordDictionary{
private:
    struct TrieNode{
        bool isWord;
        vector 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 &nums)
    {
        if (nums.size() <2)    return 0;
        int maxNum = 0;
        int flag = 0;
        for(int i = 31; i>=0; --i){
            set hash;

            flag |= (1 <=0; --i){
            int flag = (x & (1<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<next[flag] != nullptr){
                result |= (1<next[flag];
            }
            else
                root = root->next[1-flag];
        }
        return result;
    }
    int findMaximumXOR(vector& 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 
#include 

using namespace std;

//前缀树的程序表示
class TrieNode {
public:
	bool isWord;//当前节点为结尾是否是字符串
	vector 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> boardFlag;//标记board[row][col]是否已使用
	//以board[row][col]为中心点，四个方向进行尝试搜索
	void dfs(vector>& board, vector &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 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 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 findWords(vector>& board, vector& words) {
		rowSize = board.size();
		if (rowSize == 0) {
			return {};
		}
		colSize = board[0].size();
		boardFlag = vector>(rowSize, vector(colSize, false));//构建标记容器
		trieRoot = new TrieNode();//单词后缀树
        //将单词都放入前缀树中
		for (auto word : words) {
			addWord(word);
		}
		vector result;//用于存储结果
		string tempRes;
		for (int row = 0; row 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 
#include 
#include 
#include 

using namespace std;

class Solution{
public: 
    bool isPalindrome(string& s, int start, int end){
        while(start > palindromePairs(vector words){
        vector> ans;
        unordered_map dict;
        int len = words.size();
        for(int i=0; i0 && 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 a = {"lls", "s", "sssll"};
    Solution s = Solution();
    vector> v =  s.palindromePairs(a);
};