438.Find All Anagrams in a String

Tags: [sliding_window], [map]

Link: https://leetcode.com/problems/find-all-anagrams-in-a-string/?tab=Description

Given a stringsand anon-emptystringp, find all the start indices ofp's anagrams ins.

Strings consists of lowercase English letters only and the length of both stringssandpwill not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Solution: sliding window, map

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        if not s or not p or len(s) < len(p):
            return []

        p_map = {}
        for c in p:
            if c in p_map:
                p_map[c] += 1
            else:
                p_map[c] = 1

        moving_window = {}
        for i in xrange(len(p)):
            c = s[i]
            if c in moving_window:
                moving_window[c] += 1
            else:
                moving_window[c] = 1

        result = []
        for start in xrange(len(s) - len(p) + 1):
            if self.are_equal_maps(p_map, moving_window):
                result.append(start)

            end = start + len(p) - 1

            # update moving window
            start_c = s[start]
            moving_window[start_c] -= 1
            if not moving_window[start_c]:
                del moving_window[start_c]

            if end + 1 >= len(s):
                break

            next_end_c = s[end + 1]
            if next_end_c in moving_window:
                moving_window[next_end_c] += 1
            else:
                moving_window[next_end_c] = 1

        return result

    def are_equal_maps(self, map1, map2):
        if not map1:
            return not map2
        if not map2:
            return not map1
        if len(map1) != len(map2):
            return False

        for k1 in map1:
            if k1 not in map2 or map1[k1] != map2[k1]:
                return False

        return True

Revelation:

• We don't need to rebuild map each time, we can use sliding_window map, the pull start element out, and push the next end element into the 'window'.

Note:

• Time complexity = O(n), n is the number of the characters of the given string s.

Time Limited Exceeded

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        if not s or len(s) < len(p):
            return []

        p_map = {}
        for c in p:
            if c in p_map:
                p_map[c] += 1
            else:
                p_map[c] = 1

        s_len = len(s)
        start = 0
        end = 0
        result = []
        tmp_p_map = dict(p_map)
        while end < s_len:
            if not tmp_p_map:
                result.append(start)
                start += 1
                end = start
                tmp_p_map = dict(p_map)
            else:
                curr = s[end]
                if curr not in tmp_p_map:
                    start += 1
                    end = start
                    tmp_p_map = dict(p_map)
                else:
                    tmp_p_map[curr] -= 1
                    if not tmp_p_map[curr]:
                        del tmp_p_map[curr]
                    end += 1

        if not tmp_p_map:
            result.append(start)

        return result

Note:

• Time complexity = O(n * m), n is the length of the string s, and m is the length of the string p.

Time Limited Exceeded

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        if not s or len(s) < len(p):
            return []

        # do counting chars on p
        p_map = self.counting(p)

        result = []
        s_len = len(s)
        p_len = len(p)
        for start in xrange(s_len - p_len + 1):
            sub_s = s[start:start + p_len]
            sub_s_map = self.counting(sub_s)
            if self.are_equal_maps(p_map, sub_s_map):
                result.append(start)

        return result

    def counting(self, s):
        c_map = {}
        if not s:
            return c_map

        for c in s:
            if c in c_map:
                c_map[c] += 1
            else:
                c_map[c] = 1

        return c_map

    def are_equal_maps(self, map1, map2):
        if not map1:
            return not map2
        if not map2:
            return not map1
        if len(map1) != len(map2):
            return False

        for k1 in map1:
            if k1 not in map2 or map1[k1] != map2[k1]:
                return False

        return True

Note:

• Time complexity = O(n * m), n is the length of the string s, and m is the length of the string p.