290. Word Pattern

// 演算法 / Algorithm:
// 用兩個方向的對應表驗證「字母 ↔ 單字」是雙射。
// char2word[26] 存每個字母對應的單字；用一個雜湊集合記住每個單字已被哪個字母佔用。
// 邊用 strtok 切單字，邊逐字母比對；任何不一致即回傳 false。
// We verify a letter↔word bijection with two-way mapping. char2word holds each
// letter's word; a small hash set remembers which letter owns each word.

#include <stdbool.h>   // 提供 bool / true / false / gives us the bool type
#include <string.h>    // 提供 strtok, strcmp, strdup / string helpers
#include <stdlib.h>    // 提供 malloc, free / memory helpers

// 簡單雜湊表節點：把「單字 → 佔用它的字母」存成鏈結串列
// A hash-table node mapping a word to the letter that owns it.
typedef struct Node {
    char *word;          // 單字字串 / the word text
    char letter;         // 佔用此單字的字母 / the letter that claimed this word
    struct Node *next;   // 同一個桶內的下一個節點 / next node in the same bucket
} Node;

#define BUCKETS 1024     // 雜湊桶數量，取 2 的次方方便用 & 取餘 / number of buckets

// 字串雜湊函式：把單字轉成一個桶的索引
// String hash: turn a word into a bucket index.
static unsigned hashStr(const char *s) {
    unsigned h = 5381;                       // djb2 常見起始值 / classic djb2 seed
    for (; *s; s++)                          // 逐字元 / walk each character
        h = h * 33 + (unsigned char)*s;      // 經典 djb2 混合 / djb2 mixing step
    return h & (BUCKETS - 1);                // 取桶索引（等同 % BUCKETS）/ bucket index
}

bool wordPattern(char *pattern, char *s) {
    char *char2word[26] = {0};   // 字母→單字，初值全為 NULL 代表「尚未對應」/ letter→word, NULL = unmapped
    Node *buckets[BUCKETS] = {0};// 單字→字母 的雜湊表，全部桶先清空 / word→letter hash table, empty
    bool ok = true;              // 最終答案，先假設成立 / answer, assume true until proven false

    int pi = 0;                  // pattern 的索引（第幾個字母）/ index into pattern
    int plen = (int)strlen(pattern); // pattern 長度，最後比對單字數用 / pattern length

    // strtok 會就地切割 s，所以複製一份避免破壞輸入
    // strtok modifies s in place, so copy it to keep the original intact.
    char *copy = strdup(s);      // strdup = malloc + 複製字串 / duplicate the string

    // strtok：第一次傳字串，之後傳 NULL，會依分隔符 " " 逐段回傳單字
    // strtok: first call passes the string, later calls pass NULL to keep going.
    char *word = strtok(copy, " ");

    while (word != NULL) {       // 還有單字就繼續 / loop while words remain
        if (pi >= plen) {        // 單字比字母多 → 不可能匹配 / more words than letters
            ok = false;
            break;
        }
        char c = pattern[pi];            // 目前要配對的字母 / current letter
        int li = c - 'a';                // 把 'a'..'z' 轉成 0..25 當陣列索引 / letter as 0..25

        // --- 檢查正向：字母 → 單字 ---
        // Check forward direction: letter → word.
        if (char2word[li] != NULL) {                 // 這個字母以前對應過 / letter seen before
            if (strcmp(char2word[li], word) != 0) {  // 但單字不同 → 矛盾 / different word now
                ok = false;
                break;
            }
            // 一致就不必動表，直接看下一個 / consistent, fall through
        } else {
            // --- 字母是新的：先確認這個單字沒被別的字母佔走（反向）---
            // New letter: make sure no other letter already owns this word (reverse).
            unsigned b = hashStr(word);              // 找到單字所在的桶 / locate bucket
            Node *cur = buckets[b];
            char owner = 0;                          // 0 代表「沒人佔用」/ 0 means unowned
            while (cur) {                            // 走訪桶內鏈結串列 / scan the chain
                if (strcmp(cur->word, word) == 0) {  // 找到相同單字 / found this word
                    owner = cur->letter;             // 記下佔用者 / record its owner letter
                    break;
                }
                cur = cur->next;
            }
            if (owner != 0 && owner != c) {          // 單字已被「別的」字母佔走 / word taken by another letter
                ok = false;
                break;
            }
            if (owner == 0) {                        // 真的是新單字才插入反向表 / brand-new word → insert
                Node *n = (Node *)malloc(sizeof(Node)); // 配置節點 / allocate node
                n->word = strdup(word);              // 複製單字（copy 之後會被釋放）/ own a copy of the word
                n->letter = c;                       // 記住佔用字母 / store owning letter
                n->next = buckets[b];                // 頭插法接到桶上 / push to front of bucket
                buckets[b] = n;
            }
            char2word[li] = word;                    // 建立正向對應（指向 copy 內字串）/ set forward map
        }

        pi++;                            // 換下一個字母 / advance letter index
        word = strtok(NULL, " ");        // 取下一個單字 / grab next word
    }

    // 走完後，字母數必須剛好等於單字數，否則字母比單字多 → false
    // After the loop, letters and words must be equal in count.
    if (ok && pi != plen) ok = false;    // pi 是已用掉的字母數 / pi = letters consumed

    // 釋放反向表所有節點與字串，避免記憶體洩漏
    // Free every node and its duplicated word to avoid leaks.
    for (int b = 0; b < BUCKETS; b++) {
        Node *cur = buckets[b];
        while (cur) {
            Node *nxt = cur->next;       // 先存下一個再釋放當前 / save next before freeing
            free(cur->word);             // 釋放複製的單字 / free duplicated word
            free(cur);                   // 釋放節點本身 / free the node
            cur = nxt;
        }
    }
    free(copy);                          // 釋放整份字串副本 / free the string copy

    return ok;                           // 回傳結果 / return the verdict
}

// 演算法 / Algorithm:
// 用兩張 unordered_map 維護「字母→單字」與「單字→字母」兩個方向的對應，
// 一邊用 istringstream 切詞一邊比對；任一方向衝突即 false，最後字數必須相等。
// Two unordered_maps track letter→word and word→letter; we split words with a
// stringstream and check both directions, requiring equal counts at the end.

#include <string>
#include <sstream>          // istringstream：方便用空格切詞 / split words by spaces
#include <unordered_map>    // 雜湊表 / hash maps

class Solution {
public:
    bool wordPattern(std::string pattern, std::string s) {
        // 兩張對應表 / the two mapping tables
        std::unordered_map<char, std::string> char2word; // 字母 → 單字 / letter → word
        std::unordered_map<std::string, char> word2char; // 單字 → 字母 / word → letter

        std::istringstream iss(s); // 把 s 包成可逐詞讀取的串流 / wrap s as a token stream
        std::string word;          // 暫存當前單字 / holds the current word
        size_t i = 0;              // 目前對到 pattern 的第幾個字母 / index into pattern

        // iss >> word 每次讀出一個以空白分隔的單字，讀完回傳 false 結束迴圈
        // `iss >> word` extracts one whitespace-separated word each loop.
        while (iss >> word) {
            if (i >= pattern.size()) return false; // 單字比字母多 / more words than letters
            char c = pattern[i];                   // 當前字母 / current letter

            // auto + find：在表中查 c；it == end() 代表「沒找到」
            // `find` returns an iterator; == end() means "not present".
            auto fw = char2word.find(c);
            if (fw != char2word.end()) {
                // 字母已對應過，必須是同一個單字 / letter mapped before → must match
                if (fw->second != word) return false; // fw->second 是對應的單字 / its word
            } else {
                // 字母是新的：確認單字未被別的字母佔用 / new letter → word must be free
                auto rv = word2char.find(word);
                if (rv != word2char.end()) {
                    // 單字已被某字母佔用，且不是 c → 衝突 / word owned by another letter
                    if (rv->second != c) return false;
                } else {
                    // 兩個方向都是全新，建立雙向對應 / brand-new pair → record both ways
                    char2word[c] = word;   // operator[] 不存在就插入 / insert forward
                    word2char[word] = c;   // 插入反向 / insert reverse
                }
            }
            ++i; // 換下一個字母 / advance to next letter
        }

        // 字母數必須等於單字數，否則字母比單字多 → false
        // Letters must equal words; leftover letters mean no full match.
        return i == pattern.size();
    }
};