January 17, 2022: word rule II. Give you a pattern and a character

2022-01-17： Rules of words II.

Give you a rule pattern And a string str, Please judge str Whether to follow the same rules .

Here we mean Follow exactly , for example pattern Each letter and string in str Each of them Non empty Between words , There is a corresponding law of two-way connection .

Power button 291.

answer 2022-01-17：

recursive .str=abcabc,pattern=xx. First, let a=x, let ab=x, let abc=x. Until the exact match .

The code to use golang To write . The code is as follows ：

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 and pattern, It's not all over ！
    if pi == len(p) || si == len(s) {
        return false
    }
    //  str and pattern, It's not over ！

    //char ch = p.charAt(pi);
    ch := p[pi]
    cur := map0[ch-'a']
    if cur != "" { //  At present p[pi] It has been specified ！
        return si+len(cur) <= len(s) && //  Don't cross the border ！
            cur == s[si:si+len(cur)] &&
            match(s, p, si+len(cur), pi+1, map0, set)
    }
    // p[pi] It's not specified ！
    end := len(s)
    //  prune ！ Important pruning ！
    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++ {
        //   from si All prefix strings starting , Full test 
        cur = s[si : i+1]
        //  however , Only this prefix string , I haven't occupied any other pit before ！ To try 
        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
}

The results are as follows ：

picture

Zuo Shen java Code

moonfdd