438. Find All Anagrams in a String

#HashTable #String #SlidingWindow

 

두 문자열 s와 p가 주어진다. 이 때 p의 모든 문자가 사용된 s의 시작 인덱스를 리스트로 반환한다.

단, 반환하는 리스트 안의 요소 순서는 상관이 없다.

 

* 애너그램(Anagram)이란?

단어나 구의 글자를 재배치하여 만든 단어나 구문으로, 모든 글자를 한 번씩만 사용한다.

 

예시:

(Input) s = "cbaebabacd", p = "abc"
(Output) [0,6]

 

---

Trial 1 : Python3, 22/02/02

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = []
        psorted = sorted(p)
        for i in range(len(s)):
            ssorted = sorted(s[i:i+len(p)])
            if ssorted == psorted:
                result.append(i)
        return result

풀이:

p의 모든 문자가 포함되어야 하며, s 안에서 p의 문자가 사용되는 순서가 정해져있지 않기 때문에

일관성을 위해서 비교에 필요한 부분들을 정렬해서 사용하기로 했다.

s 안에서 필요한 부분을 얻기 위해서 문자열 슬라이싱 기능을 사용했다.

p 문자열을 정렬하고 슬라이싱으로 s 문자열에서 필요한 부분을 얻은 후 마찬가지로 정렬한다.

그 다음 둘을 비교하고 같다면 결과로 반환할 리스트에 해당 인덱스를 추가한다.

 

리뷰: 

테스트셋에서는 통과했지만 전체를 돌렸을 때 타임리밋에 걸렸다.

문자열을 슬라이싱하는 방법을 사용하다보니 너무 긴 문자열이 주어졌을 경우에 발생하는 현상 같은데

별다른 방법이 떠오르지 않아서 나중에 다시 풀어볼 예정이다.

반환하는 리스트 안의 값 순서가 상관없다는 조건이 붙었고, 카테고리에 HashTable이 있는데

이번 풀이에서는 사용하지 않았기 때문에 다음에 풀어볼 때는 이 둘에 포인트를 두고 풀어봐야겠다.