[leetcode-242] Valid Anagram

LeetCode-242

Valid Anagram : info

note : sub

the two strings contain the same letters, but the order of the letters may be different.

        :::python

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s)!=len(t):
        return False
        for i in s:
            if i not in t:
                return False
            else:
                t = t.replace(i,'',1)
        return True

Result : 59ms Memory: 16.8mb

문제 이해

주어진 문자열 s와 t가 주어졌을 때, s의 문자를 재배열하여 t를 얻을 수 있는지 여부를 반환하는 문제입니다. 즉, s와 t는 알파벳의 종류와 개수가 동일해야 합니다.

문제 해결 방법

주어진 문자열에서 알파벳의 개수와 종류가 동일한지 비교해야 합니다. 이를 위해 두 문자열의 길이가 같은지 확인한 뒤, for 문을 이용해 s 문자열의 모든 문자에 대해 t에 포함되어 있는지 확인합니다. t에서 뽑은 문자를 하나씩 삭제하며 문자열이 동일한지 검사합니다.

사용자 코드 분석

주어진 코드에서는 s의 모든 문자에 대해 t에 포함되어 있는지 하나씩 확인합니다. t에서 삭제되는 과정에서 시간 복잡도가 O(n^2)이 나오므로, 문자열 길이가 길수록 실행 시간이 길어집니다.

추천 코드

다음은 Counter 라이브러리를 이용한 추천 코드입니다. Counter 함수를 이용하면 두 문자열에서 알파벳의 종류와 개수를 세어 딕셔너리 형태로 반환합니다. 이후 두 딕셔너리를 비교해 두 문자열이 동일한지 파악할 수 있습니다.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return collections.Counter(s) == collections.Counter(t)

이 코드를 이용하면 문자열 길이가 길어져도 실행 시간이 느려지지 않습니다. 하지만 이 코드 또한 선형 시간이 소요되므로, 문자열 길이가 굉장히 길어질 경우 해시 테이블 구조를 이용해 문자열의 알파벳을 카운트하는 방법도 고려해 볼 수 있습니다.