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

目录

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 mainimport ("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] = ws2p[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 mainimport ("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] = wused[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 mainimport ("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] = wordused[word] = trueif 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 mainimport ("fmt""strings"
)func wordPatternMatch(pattern string, s string) bool {p2s := make(map[byte]string)s2p := make(map[string]byte)var match func(int, int) boolmatch = 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 stringfor i := si; i < len(s); i++ {word = s[si : i+1]_, ok = s2p[word]if !ok {p2s[pattern[pi]] = words2p[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）暂停更