原題地址:字模式
給定一個(gè)模式串pattern和一個(gè)字符串str，請(qǐng)問(wèn)str和pattern是否遵循相同的模式钥顽。
這里遵循模式指的是一個(gè)完全匹配义屏，即在pattern中的每個(gè)不同的字母和str中每個(gè)非空的單詞之間有一個(gè)雙向映射的模式對(duì)應(yīng)。您可以認(rèn)為模式串pattern只包含小寫(xiě)字母蜂大，而str包含由單個(gè)空間分隔的小寫(xiě)單詞組成闽铐。
因?yàn)橐灰粚?duì)應(yīng)的關(guān)系，所以要雙向映射奶浦，所以需要兩個(gè)map: 一個(gè)從pattern的字符到對(duì)應(yīng)的單詞兄墅，一個(gè)從單詞到字符。
這里我沒(méi)有使用系統(tǒng)的map,而是實(shí)現(xiàn)了一個(gè) 前綴樹(shù) 來(lái)練練手澳叉，對(duì)于一個(gè)前綴樹(shù)隙咸，一個(gè)節(jié)點(diǎn)可以和一個(gè)單詞做一一對(duì)應(yīng)的映射沐悦，對(duì)應(yīng)的單詞就是從跟沿著路徑到這個(gè)節(jié)點(diǎn)的那個(gè)單詞。所以可以在這個(gè)節(jié)點(diǎn)里存入跟單詞對(duì)應(yīng)的數(shù)據(jù)五督，就可以實(shí)現(xiàn)從單詞到這個(gè)數(shù)據(jù)的映射藏否，所以這里存入字符，實(shí)現(xiàn)從單詞到pattern的字符的映射充包。
從字符到單詞的映射副签，有多個(gè)方案：
- unordered_map<char, string>，用char做key, word做value
- 因?yàn)槎际切?xiě)字母误证，所以可以用 string[26]來(lái)標(biāo)記继薛，string[c-'a']就可以得到字符c的word，比較
- 因?yàn)榍熬Y樹(shù)里節(jié)點(diǎn)跟單詞一一對(duì)應(yīng)愈捅，所以可以直接存入節(jié)點(diǎn)遏考，結(jié)合2的思路就是：TrieNode[26]. 相比2的好處是，比較單詞相等不用string.compare了蓝谨，直接比較兩個(gè)節(jié)點(diǎn)是否相等就可以了灌具。前綴樹(shù)是節(jié)點(diǎn)不會(huì)刪除，讓這一點(diǎn)成為了可能譬巫。這樣做復(fù)雜度直接從O(N*L)到了O(N)咖楣，L是字符串的平均長(zhǎng)度。
using namespace std;
namespace TFDataStruct {
template<class T>
class Trie{
public:
struct TrieNode{
char ch;
//對(duì)應(yīng)的字符串的個(gè)數(shù)
uint32_t mark = 0;
T relateData; //做額外的數(shù)據(jù)處理
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);
}
}
/** 插入一個(gè)元素芦昔，同時(shí)最后的節(jié)點(diǎn) */
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. 前綴樹(shù)記錄的是單詞到字符的對(duì)應(yīng)關(guān)系诱贿，每個(gè)節(jié)點(diǎn)唯一對(duì)應(yīng)一個(gè)單詞(即從跟到這個(gè)節(jié)點(diǎn)的路徑拼起來(lái)的單詞),所以用節(jié)點(diǎn)存儲(chǔ)單詞映射的字符；
//2. markC2W[c]表示c這個(gè)字符映射的單詞咕缎，又因?yàn)楣?jié)點(diǎn)和單詞的一一對(duì)應(yīng)關(guān)系珠十，所以把單詞對(duì)應(yīng)的節(jié)點(diǎn)存入
TFDataStruct::Trie<char> trieW2C;
TFDataStruct::Trie<char>::TrieNode* charNodes[256];
memset(charNodes, 0, sizeof(charNodes));
//3. 因?yàn)橐灰粚?duì)應(yīng)的關(guān)系，1和2剛好是兩個(gè)方向
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;
}
};
