目录
290. 单词规律 Word Pattern 🌟
291. 单词规律 II Word Pattern ii 🌟🌟
🌟 每日一练刷题专栏 🌟
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
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 <= 300pattern 和 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）暂停更文章来源地址https://www.toymoban.com/news/detail-500213.html |
文章来源：https://www.toymoban.com/news/detail-500213.html到了这里，关于Golang每日一练(leetDay0099) 单词规律I\II Word Pattern的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
