网站应该怎么建设,深圳做网站公司有哪些企业,用dw做音乐网站,深圳新闻前言
接前文 滑动窗口算法 - LC76 最小覆盖子串-CSDN博客#xff0c;此题也是套用滑窗模板#xff0c;但是在两个细节点处稍有不同。
正文
LCR 014. 字符串的排列
给定两个字符串 s1 和 s2#xff0c;写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说#xf…前言
接前文 滑动窗口算法 - LC76 最小覆盖子串-CSDN博客此题也是套用滑窗模板但是在两个细节点处稍有不同。
正文
LCR 014. 字符串的排列
给定两个字符串 s1 和 s2写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说第一个字符串的排列之一是第二个字符串的 子串 。
题解
func checkInclusion(s2 string, s1 string) bool {window : make(map[byte]int)need : make(map[byte]int)for i : 0; i len(s2); i {need[s2[i]]}n : len(s1)l, r : 0, 0valid : 0for r n {c : s1[r]rif need[c] 0 {window[c]if need[c] window[c] {valid}}for r-l len(s2) {if valid len(need) {return true}d : s1[l]lif need[d] 0 {if need[d] window[d] {valid--}window[d]--}}}return false
}
细节点
1注意窗口收缩的条件发生改变即左指针移动的条件发生改变只要当前窗口的长度目标字符串的长度即l-r len(s2)注意不是l-r len(need)那么就开始收缩因为我们要找的覆盖子串是要和目标字符串长度相等的不同排列。
2len(need)是目标字符串里不重复元素个数len(s2)是目标字符串长度当r-l len(s2)并且validlen(need)时说明在s1中找到了s2的不同排列的字符串所以可以直接return true。
