package main

import "fmt"

func main() {
    ret := wordPatternMatch("abab", "redblueredblue")
    fmt.Println(ret)
}

func wordPatternMatch(pattern, str string) bool {
    return match(str, pattern, 0, 0, make([]string, 26), make(map[string]struct{}))
}

func match(s, p string, si, pi int, map0 []string, set map[string]struct{}) bool {
    if pi == len(p) && si == len(s) {
        return true
    }
    // str和pattern，并没有都结束！
    if pi == len(p) || si == len(s) {
        return false
    }
    //  str和pattern，都没结束！

    //char ch = p.charAt(pi);
    ch := p[pi]
    cur := map0[ch-'a']
    if cur != "" { // 当前p[pi]已经指定过了！
        return si+len(cur) <= len(s) && // 不能越界！
            cur == s[si:si+len(cur)] &&
            match(s, p, si+len(cur), pi+1, map0, set)
    }
    // p[pi]没指定！
    end := len(s)
    // 剪枝！重要的剪枝！
    for i := len(p) - 1; i > pi; i-- {
        //end -= map0[p[i] - 'a'] == nil ? 1 : len(map0[p[i]-'a'])
        if map0[p[i]-'a'] == "" {
            end -= 1
        } else {
            end -= len(map0[p[i]-'a'])
        }

    }
    for i := si; i < end; i++ {
        //  从si出发的所有前缀串，全试
        cur = s[si : i+1]
        // 但是，只有这个前缀串，之前没占过别的坑！才能去尝试
        if _, ok := set[cur]; !ok {
            //set.add(cur);
            set[cur] = struct{}{}
            map0[ch-'a'] = cur
            if match(s, p, i+1, pi+1, map0, set) {
                return true
            }
            map0[ch-'a'] = ""
            //set.remove(cur);
            delete(set, cur)
        }
    }
    return false
}