438. Find All Anagrams in a String

1. Description

• Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

2. Example

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”.

3. Solution

1. 첫번째 풀이
   • 📌제한시간 20분내에 맞춰서 풀지는 못했으나 작은 문제였어서 바로 풀어냈다.
   • Runtime: 6958ms
   • 설명:
     • for문의 범위를 s의 길이에서 p의 길이를 빼고 1을 더한 값으로 정한다.
       • range(num)가 0부터 num-1까지의 범위를 나타내니 거기에 +1을 하면 마지막숫자까지 나타날 수 있다.
     • if s[i] in p:: p에 s[i]가 없다면 그다음 문자로 넘어간다.
     • sorted_str = sorted(s[i:i+len_p]): p의 길이만큼 s를 슬라이싱을 하여 정렬한다.
     • 정렬된 값이 정렬된 p값과 같다면 i를 append한다.

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        len_p = len(p)
        sorted_p = sorted(p)
        ans = []
 
        for i in range(len(s) - len_p+1):
            if s[i] in p:
                sorted_str = sorted(s[i:i+len_p])
                if sorted_str == sorted_p:
                    ans.append(i)
        return ans

2. 두번째 풀이

4. What I Learned

References

문자열 인덱싱 및 슬라이싱