原題地址:字模式

給定一個(gè)模式串pattern和一個(gè)字符串str，請(qǐng)問str和pattern是否遵循相同的模式。
這里遵循模式指的是一個(gè)完全匹配，即在pattern中的每個(gè)不同的字母和str中每個(gè)非空的單詞之間有一個(gè)雙向映射的模式對(duì)應(yīng)。

您可以認(rèn)為模式串pattern只包含小寫字母，而str包含由單個(gè)空間分隔的小寫單詞組成。

因?yàn)橐灰粚?duì)應(yīng)的關(guān)系，所以要雙向映射，所以需要兩個(gè)map: 一個(gè)從pattern的字符到對(duì)應(yīng)的單詞，一個(gè)從單詞到字符。

這里我沒有使用系統(tǒng)的map,而是實(shí)現(xiàn)了一個(gè) 前綴樹 來練練手，對(duì)于一個(gè)前綴樹，一個(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è)方案：

1. unordered_map<char, string>，用char做key, word做value
2. 因?yàn)槎际切懽帜?，所以可以?string[26]來標(biāo)記，string[c-'a']就可以得到字符c的word，比較
3. 因?yàn)榍熬Y樹里節(jié)點(diǎn)跟單詞一一對(duì)應(yīng)，所以可以直接存入節(jié)點(diǎn)，結(jié)合2的思路就是：TrieNode[26]. 相比2的好處是，比較單詞相等不用string.compare了，直接比較兩個(gè)節(jié)點(diǎn)是否相等就可以了。前綴樹是節(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. 前綴樹記錄的是單詞到字符的對(duì)應(yīng)關(guān)系，每個(gè)節(jié)點(diǎn)唯一對(duì)應(yīng)一個(gè)單詞(即從跟到這個(gè)節(jié)點(diǎn)的路徑拼起來的單詞),所以用節(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;
}
};