Golang每日一练(leetDay0099) 单词规律I\II Word Pattern

290. 单词规律 Word Pattern

给定一种规律

pattern

和一个字符串

s

，判断

s

是否遵循相同的规律。

这里的 **遵循 **指完全匹配，例如，

pattern

里的每个字母和字符串

str

** **中的每个非空单词之间存在着双向连接的对应规律。

示例1:

**输入:** pattern = "abba", str = "dog cat cat dog"
**输出:** true

示例 2:

**输入:**pattern = "abba", str = "dog cat cat fish"
**输出:** false

示例 3:

**输入:** pattern = "aaaa", str = "dog cat cat dog"
**输出:** false

提示:

• 1 <= pattern.length <= 300
• pattern 只包含小写英文字母
• 1 <= s.length <= 3000
• s 只包含小写英文字母和 ' '
• s 不包含 任何前导或尾随对空格
• s 中每个单词都被 **单个空格 **分隔

代码1：

package main

import (
    "fmt"
    "strings"
)

func wordPattern(pattern string, s string) bool {
    words := strings.Split(s, " ")
    if len(pattern) != len(words) {
        return false
    }
    p2s := make(map[byte]string)
    s2p := make(map[string]byte)
    for i := 0; i < len(pattern); i++ {
        p, w := pattern[i], words[i]
        if s, ok := p2s[p]; ok {
            if s != w {
                return false
            }
        } else {
            if _, ok := s2p[w]; ok {
                return false
            }
            p2s[p] = w
            s2p[w] = p
        }
    }
    return true
}

func main() {
    pattern := "abba"
    s := "dog cat cat dog"
    fmt.Println(wordPattern(pattern, s))
    pattern = "abba"
    s = "dog cat cat fish"
    fmt.Println(wordPattern(pattern, s))
    pattern = "aaaa"
    s = "dog cat cat dog"
    fmt.Println(wordPattern(pattern, s))
}

代码2：

package main

import (
    "fmt"
    "strings"
)

func wordPattern(pattern string, s string) bool {
    words := strings.Split(s, " ")
    if len(pattern) != len(words) {
        return false
    }
    p2s := make(map[byte]string)
    used := make(map[string]bool)
    for i := 0; i < len(pattern); i++ {
        p, w := pattern[i], words[i]
        if s, ok := p2s[p]; ok {
            if s != w {
                return false
            }
        } else {
            if used[w] {
                return false
            }
            p2s[p] = w
            used[w] = true
        }
    }
    return true
}

func main() {
    pattern := "abba"
    s := "dog cat cat dog"
    fmt.Println(wordPattern(pattern, s))
    pattern = "abba"
    s = "dog cat cat fish"
    fmt.Println(wordPattern(pattern, s))
    pattern = "aaaa"
    s = "dog cat cat dog"
    fmt.Println(wordPattern(pattern, s))
}

输出：

true
false
false

291. 单词规律 II Word Pattern ii

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

这里我们指的是 完全遵循，例如 pattern 里的每个字母和字符串 str 中每个 非空 单词之间，存在着 双射 的对应规律。双射 意味着映射双方一一对应，不会存在两个字符映射到同一个字符串，也不会存在一个字符分别映射到两个不同的字符串。

示例1:

**输入:** pattern = "abab", str = "redblueredblue"
**输出:** true
**解释：**一种可能的映射如下：'a'->"red",'b'->"blue"

示例 2:

**输入: **pattern = "aaaa", str = "asdasdasdasd"
**输出:** true
**解释：**一种可能的映射如下：'a'->"asd"

示例 3:

**输入: **pattern = "abab", str = "asdasdasdasd"
**输出:** true
**解释：**一种可能的映射如下：'a'->"a",'b'->"sdasd"
注意 'a' 和 'b' 不能同时映射到 "asd"，因为这里的映射是一种双射。

示例 4:

**输入:** pattern = "aabb", str = "xyzabcxzyabc"
**输出:** false

提示:

• 1 <= pattern.length <= 300
• pattern 和 str 都只会包含小写字母
• 1 <= str.length <= 3000

代码1： 回溯法

package main

import (
    "fmt"
    "strings"
)

func wordPatternMatch(pattern string, str string) bool {
    return backtrack(pattern, str, make(map[string]string), make(map[string]bool))
}

func backtrack(pattern, str string, dict map[string]string, used map[string]bool) bool {
    if pattern == "" {
        return str == ""
    }
    char := string(pattern[0])
    if word, ok := dict[char]; ok {
        if !strings.HasPrefix(str, word) {
            return false
        }
        return backtrack(pattern[1:], str[len(word):], dict, used)
    }
    for i := 1; i <= len(str); i++ {
        word := str[:i]
        if used[word] {
            continue
        }
        dict[char] = word
        used[word] = true
        if backtrack(pattern[1:], str[i:], dict, used) {
            return true
        }
        delete(dict, char)
        delete(used, word)
    }
    return false
}

func main() {
    fmt.Println(wordPatternMatch("abab", "redblueredblue"))
    fmt.Println(wordPatternMatch("aaaa", "asdasdasdasd"))
    fmt.Println(wordPatternMatch("abab", "asdasdasdasd"))
    fmt.Println(wordPatternMatch("aabb", "xyzabcxzyabc"))
}

代码2： 哈希表

package main

import (
    "fmt"
    "strings"
)

func wordPatternMatch(pattern string, s string) bool {
    p2s := make(map[byte]string)
    s2p := make(map[string]byte)
    var match func(int, int) bool
    match = func(pi, si int) bool {
        if pi == len(pattern) {
            return si == len(s)
        }
        p, ok := p2s[pattern[pi]]
        if ok {
            if !strings.HasPrefix(s[si:], p) {
                return false
            }
            return match(pi+1, si+len(p))
        }
        var word string
        for i := si; i < len(s); i++ {
            word = s[si : i+1]
            _, ok = s2p[word]
            if !ok {
                p2s[pattern[pi]] = word
                s2p[word] = pattern[pi]
                if match(pi+1, i+1) {
                    return true
                }
                delete(p2s, pattern[pi])
                delete(s2p, word)
            }
        }
        return false
    }
    return match(0, 0)
}

func main() {
    fmt.Println(wordPatternMatch("abab", "redblueredblue"))
    fmt.Println(wordPatternMatch("aaaa", "asdasdasdasd"))
    fmt.Println(wordPatternMatch("abab", "asdasdasdasd"))
    fmt.Println(wordPatternMatch("aabb", "xyzabcxzyabc"))
}

输出：

true
true
true
false

🌟 每日一练刷题专栏 🌟

✨持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

✎ 评论，你的意见是我进步的财富！

☸ 主页：https://hannyang.blog.csdn.net/

Rust每日一练 专栏

（2023.5.16~）更新中...

Golang每日一练 专栏

（2023.3.11~）更新中...

Python每日一练 专栏

（2023.2.18~2023.5.18）暂停更

C/C++每日一练 专栏

（2023.2.18~2023.5.18）暂停更

Java每日一练 专栏

（2023.3.11~2023.5.18）暂停更