网站建设承诺,想做企业网站,怎么才能百度到自己的网站,公司网站如何维护目录
290. 单词规律 Word Pattern #x1f31f;
291. 单词规律 II Word Pattern ii #x1f31f;#x1f31f;
#x1f31f; 每日一练刷题专栏 #x1f31f;
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C每日一练 专栏
Java每日一练 专栏 … 目录
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 300pattern 只包含小写英文字母1 s.length 3000s 只包含小写英文字母和 s 不包含 任何前导或尾随对空格s 中每个单词都被 单个空格 分隔
代码1
package mainimport (fmtstrings
)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 : abbas : dog cat cat dogfmt.Println(wordPattern(pattern, s))pattern abbas dog cat cat fishfmt.Println(wordPattern(pattern, s))pattern aaaas dog cat cat dogfmt.Println(wordPattern(pattern, s))
}代码2
package mainimport (fmtstrings
)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 : abbas : dog cat cat dogfmt.Println(wordPattern(pattern, s))pattern abbas dog cat cat fishfmt.Println(wordPattern(pattern, s))pattern aaaas dog cat cat dogfmt.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 mainimport (fmtstrings
)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 (fmtstrings
)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(pi1, silen(p))}var word stringfor i : si; i len(s); i {word s[si : i1]_, ok s2p[word]if !ok {p2s[pattern[pi]] words2p[word] pattern[pi]if match(pi1, i1) {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暂停更
