[HackerRank] Sherlock and Anagrams - Python3 풀이 (String, Medium)

• 문제 설명 🤓
  주어진 문자열의 substring 중 anagram 관계인 anagrammatic pairs의 개수 구하는 문제

• 나의 풀이 포인트 📌
  (1) 문자열 맨 앞에서부터 substring 길이 별로 계산 <- 마지막 sample을 보고 아이디어 생각
  (2) dictionary를 만들어 substring의 출현 빈도를 저장

• 알아둘 것 ⭐️
  (1) Anagram

  • Anagram이란, 한 단어를 구성하는 글자의 개수를 그대로 유지하면서 순서만 바꾼 단어이다. (ex. listen <-> silent)

  • 따라서, Anagram을 판별하기 위해서는 주로 정렬을 사용한다.
    정렬한 문자열이 같으면 anagram이다!

    (정렬 외에도 anagram을 판별하는 방법은 여러가지가 있다.
    아래 포스트가 잘 설명하고 있으니 참고! https://shoark7.github.io/programming/algorithm/several-ways-to-solve-anagram-in-python )

• 코드

def sherlockAndAnagrams(s):
    TOTAL = 0
    ana_dict = {}
    for leng in range(1, len(s)) :
        for i in range(len(s)-leng+1) :
            sub = ''.join(sorted(s[i:i+leng]))
            if sub in ana_dict.keys() :
                TOTAL += ana_dict[sub]
                ana_dict[sub] += 1
            else :
                ana_dict[sub] = 1
                
    return TOTAL