2022-01-17：单词规律 II。给你一种规律 pattern 和一个字符

原创

福大大架构师每日一题

发布于 2022-01-17 13:40:04

1540

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-01-17：单词规律 II。

给你一种规律 pattern 和一个字符串 str，请你判断 str 是否遵循其相同的规律。

这里我们指的是完全遵循，例如 pattern 里的每个字母和字符串 str 中每个非空单词之间，存在着双向连接的对应规律。

力扣291。

答案2022-01-17：

递归。str=abcabc，pattern=xx。先让a=x，再让ab=x,再让abc=x。直到完全匹配为止。

代码用golang编写。代码如下：

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
}