Given a string\u00a0s<\/b>\u00a0and a\u00a0non-empty<\/b>\u00a0string\u00a0p<\/b>, find all the start indices of\u00a0p<\/b>‘s anagrams in\u00a0s<\/b>.<\/p>\n
Strings consists of lowercase English letters only and the length of both strings\u00a0s<\/b>\u00a0and\u00a0p<\/b>\u00a0will not be larger than 20,100.<\/p>\n
The order of output does not matter.<\/p>\n
Example 1:<\/b><\/p>\n Example 2:<\/b><\/p>\n Python<\/strong><\/p>\nInput:<\/b>\r\ns: \"cbaebabacd\" p: \"abc\"\r\n\r\nOutput:<\/b>\r\n[0, 6]\r\n\r\nExplanation:<\/b>\r\nThe substring with start index = 0 is \"cba\", which is an anagram of \"abc\".\r\nThe substring with start index = 6 is \"bac\", which is an anagram of \"abc\".\r\n<\/pre>\n
Input:<\/b>\r\ns: \"abab\" p: \"ab\"\r\n\r\nOutput:<\/b>\r\n[0, 1, 2]\r\n\r\nExplanation:<\/b>\r\nThe substring with start index = 0 is \"ab\", which is an anagram of \"ab\".\r\nThe substring with start index = 1 is \"ba\", which is an anagram of \"ab\".\r\nThe substring with start index = 2 is \"ab\", which is an anagram of \"ab\".<\/pre>\n
\r\nclass Solution(object):\r\n def findAnagrams(self, s, p):\r\n """\r\n :type s: str\r\n :type p: str\r\n :rtype: List[int]\r\n """\r\n result = []\r\n if not s:\r\n return []\r\n p_dict = dict()\r\n for _p in p:\r\n Solution.add_k_in_dict(_p, p_dict)\r\n s_dict = dict()\r\n index = 0\r\n for _s in s[index: index + len(p)]:\r\n Solution.add_k_in_dict(_s, s_dict)\r\n if s_dict == p_dict:\r\n result.append(index)\r\n index += 1\r\n while index+len(p) <= len(s):\r\n print index+len(p)\r\n Solution.del_k_from_dict(s[index-1], s_dict)\r\n Solution.add_k_in_dict(s[index+len(p)-1], s_dict)\r\n if s_dict == p_dict:\r\n result.append(index)\r\n index += 1\r\n return result\r\n\r\n @classmethod\r\n def add_k_in_dict(cls, k, k_dict):\r\n if k in k_dict:\r\n k_dict[k] += 1\r\n else:\r\n k_dict[k] = 1\r\n\r\n @classmethod\r\n def del_k_from_dict(cls, k, k_dict):\r\n if k in k_dict:\r\n k_dict[k] -= 1\r\n if k_dict[k] == 0:\r\n del k_dict[k]\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"