力扣每日一题:438. 找到字符串中所有字母异位词

简介: 力扣每日一题:438. 找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词


https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/


题目:

给定一个字符串s和一个非空字符串p,找到s中所有是p的字母异位词的子串,返回这些子串的起始索引。

字符串只包含小写英文字母,并且字符串s和 p的长度都不超过 20100。

说明:

字母异位词指字母相同,但排列不同的字符串。

不考虑答案输出的顺序。


示例:

示例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" 的字母异位词。


分析:

如果做过类似题目,会第一时间想到双指针+字典的方式进行顺序比较。

  1. 维护一个ascii_lowercase为key的全零字典
  2. 根据p生成待匹配的字典信息dict_p
  3. 同理创建针对s的ascii_lowercase为key的全零字典
  4. 创建双指针,right从s[0]出发每次添加至tmp字典
  5. 当左右指针差距小于len(p)时,left指针不动
  6. 当左右指针差距等于len(p)时开始正式的对比操作,并每次匹配后left+=1
  7. 如果tmp等于dict_p,则将left指针添加入ret。
  8. 如果不匹配,删除掉左指针对应的字母。
  9. right+=1
  10. 当right指针走至s末尾结束判断。


解题:

from string import ascii_lowercase
class Solution:
    def findAnagrams(self, s, p):
        ret = []
        k_dict = {}.fromkeys(ascii_lowercase, 0)
        for i in p:
            k_dict[i] += 1
        tmp = {}.fromkeys(ascii_lowercase, 0)
        left = right = 0
        while right < len(s):
            tmp[s[right]] += 1
            if tmp == k_dict:
                ret.append(left)
            if right - left + 1 == len(p):
                tmp[s[left]] -= 1
                left += 1
            right += 1
        return ret




相关文章
|
5月前
|
存储 算法
LeetCode第49题字母异位词分组
LeetCode第49题"字母异位词分组"的解题方法,通过将每个字符串的字符排序后作为键存储在HashMap中,有效地将所有字母异位词分组。
LeetCode第49题字母异位词分组
|
3月前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
45 1
|
3月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
33 9
|
3月前
|
存储
Leetcode第49题(字母异位词分组)
LeetCode第49题要求将字符串数组中的字母异位词分组,可以通过将每个字符串排序后作为键存入哈希表,最后将哈希表中的值添加到结果列表中来实现。
26 1
|
3月前
|
算法
Leetcode第十七题(电话号码的字母组合)
这篇文章介绍了如何使用深度优先搜索(DFS)算法来解决LeetCode第17题——电话号码的字母组合问题,通过递归方法生成所有可能的字母组合。
29 0
Leetcode第十七题(电话号码的字母组合)
|
3月前
|
索引
【LeetCode 11】242.有效的字母异位词
【LeetCode 11】242.有效的字母异位词
24 0
【LeetCode 11】242.有效的字母异位词
|
3月前
|
算法
【LeetCode 52】17.电话号码的字母组合
【LeetCode 52】17.电话号码的字母组合
47 0
|
3月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
27 0
|
3月前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
37 0
|
3月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
30 0