本文主要是介绍438 找到字符串中所有字母异味词,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
·题目描述
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。示例 1:输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。示例 2:输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
·解题思路
之前的思路都是滑动窗口循环,但是事实证明想多了只需要每次对s字符串中len(p)长度的子字符串进行计数就可以了。只是计数的时候,选择使用哈希表,下标采用编码值(但是其实采用字典应该也可以)只是时间复杂度会高
·代码
分为两个部分
1.统计第一个子字符串的字母出现次数。若是与count-p相同,则增加0
2.在字符串s中,进行移位,并且统计次数
class Solution(object):def findAnagrams(self,s,p):size_s ,size_p = len(s),len(p)if size_s < size_p:return 0res = []count_s = [0] * 26count_p = [0] * 26for i in range(size_p): #首次判断count_s[ord(s[i]) - 97] += 1count_p[ord(p[i]) - 97] += 1if count_s == count_p :res.append(0)for j in range(size_s - size_p): #移位操作count_s[ord(s[j]) - 97] -= 1count_s[ord(s[j+size_p]) - 97] += 1if count_s == count_p :res.append(j+1)return res
这篇关于438 找到字符串中所有字母异味词的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!