原题地址:字模式
给定一个模式串pattern和一个字符串str，请问str和pattern是否遵循相同的模式。
这里遵循模式指的是一个完全匹配，即在pattern中的每个不同的字母和str中每个非空的单词之间有一个双向映射的模式对应。您可以认为模式串pattern只包含小写字母，而str包含由单个空间分隔的小写单词组成。
因为要一一对应的关系，所以要双向映射，所以需要两个map: 一个从pattern的字符到对应的单词，一个从单词到字符。
这里我没有使用系统的map,而是实现了一个 前缀树 来练练手，对于一个前缀树，一个节点可以和一个单词做一一对应的映射，对应的单词就是从跟沿着路径到这个节点的那个单词。所以可以在这个节点里存入跟单词对应的数据，就可以实现从单词到这个数据的映射，所以这里存入字符，实现从单词到pattern的字符的映射。
从字符到单词的映射，有多个方案：
- unordered_map<char, string>，用char做key, word做value
- 因为都是小写字母，所以可以用 string[26]来标记，string[c-'a']就可以得到字符c的word，比较
- 因为前缀树里节点跟单词一一对应，所以可以直接存入节点，结合2的思路就是：TrieNode[26]. 相比2的好处是，比较单词相等不用string.compare了，直接比较两个节点是否相等就可以了。前缀树是节点不会删除，让这一点成为了可能。这样做复杂度直接从O(N*L)到了O(N)，L是字符串的平均长度。
using namespace std;
namespace TFDataStruct {
template<class T>
class Trie{
public:
struct TrieNode{
char ch;
//对应的字符串的个数
uint32_t mark = 0;
T relateData; //做额外的数据处理
TrieNode *parent = nullptr;
unordered_map<char, TrieNode*> childern;
};
struct TrieNodeVisitor{
typedef void (*VisitFunc)(TrieNode *node, string &word, int idx);
VisitFunc visitF;
TrieNodeVisitor(VisitFunc visitF):visitF(visitF){};
};
private:
public:
TrieNode root;
Trie(){};
Trie(vector<string> &words){
for (auto &w : words){
insert(w, nullptr);
}
}
/** 插入一个元素，同时最后的节点 */
TrieNode *insert(string &word, TrieNodeVisitor visitor = nullptr){
TrieNode *node = &root;
int idx = 0;
while (idx<word.length()) {
auto &next = node->childern[word[idx]];
if (next == nullptr) {
next = new TrieNode();
next->ch = word[idx];
next->parent = node;
}
node = next;
if (visitor.visitF) visitor.visitF(node, word, idx);
idx++;
}
node->mark++;
return node;
}
int count(string &word){
TrieNode *node = &root;
int idx = 0;
while (idx<word.length()) {
auto &next = node->childern[word[idx]];
if (next == nullptr) {
return 0;
}
node = next;
idx++;
}
return node->mark;
}
bool exist(string &word){
return count(word)>0;
}
};
}
class Solution {
public:
/**
* @param pattern: a string, denote pattern string
* @param teststr: a string, denote matching string
* @return: an boolean, denote whether the pattern string and the matching string match or not
*/
bool wordPattern(string &pattern, string &teststr) {
teststr.push_back(' ');
//1. 前缀树记录的是单词到字符的对应关系，每个节点唯一对应一个单词(即从跟到这个节点的路径拼起来的单词),所以用节点存储单词映射的字符；
//2. markC2W[c]表示c这个字符映射的单词，又因为节点和单词的一一对应关系，所以把单词对应的节点存入
TFDataStruct::Trie<char> trieW2C;
TFDataStruct::Trie<char>::TrieNode* charNodes[256];
memset(charNodes, 0, sizeof(charNodes));
//3. 因为要一一对应的关系，1和2刚好是两个方向
int start=-1, i = 0;
int wordIdx = 0;
for (auto &c : teststr){
if (start<0) {
if (c!=' ') {
start = i;
}
}else{
if (c==' ') {
auto str = teststr.substr(start, i-start);
auto node = trieW2C.insert(str);
auto charNode = charNodes[pattern[wordIdx]];
if (charNode == nullptr) {
if (node->relateData>0) {
return false;
}
}else if (node != charNode) {
return false;
}
node->relateData = pattern[wordIdx];
charNodes[pattern[wordIdx]] = node;
start = -1;
wordIdx++;
}
}
i++;
}
return true;
}
};
