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 <= 300pattern只包含小写英文字母1 <= s.length <= 3000s只包含小写英文字母和' '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）暂停更 |
