242. 유효 아나그램 - Leetcode Easy

문제 설명

두 개의 문자열 s와 t가 주어지면 t가 s의 애너그램이면 true를 반환하고 그렇지 않으면 false를 반환합니다.

애너그램은 일반적으로 모든 원래 문자를 정확히 한 번만 사용하여 다른 단어나 구의 문자를 재배열하여 형성된 단어 또는 구입니다.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

접근법 1

문자와 빈도는 두 문자열에서 동일하므로 정렬 순서가 동일한지 확인합니다. 정렬된 순서가 동일하면 true를 반환할 수 있습니다.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

시간 복잡도 - O(s log s) or O(t log t) - 정렬로 인해
공간 복잡성 - O(1) - 정렬에 사용된 공간을 고려하지 않은 경우.

접근법 2

먼저 길이가 같은지 확인해야 합니다. 그렇지 않은 경우 애너그램의 길이가 동일해야 하므로 즉시 false를 반환할 수 있습니다. 다음으로 두 문자열에서 각 문자의 빈도/발생을 계산해야 합니다. 각 문자열에 대한 해시맵을 사용하여 이를 수행할 수 있습니다. 두 해시맵이 동일하면 true를 반환할 수 있습니다.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        sMap = {}
        tMap = {}

        for i in range(len(s)):
            sMap[s[i]] = sMap.get(s[i], 0) + 1 #get function on hashMap return it's value 
            tMap[t[i]] = tMap.get(t[i], 0) + 1 #or default value we specified which is 0 in this case

        if len(sMap) != len(tMap): # If lengths of hashMaps are not equal,
            return False  #it means that there is a mismatch

        for c in (sMap):
            if(sMap[c] != tMap.get(c, 0)): # In case of t not having a letter present in s,
                return False # tMap needs to give 0 there, that's why using get function there.

        return True

시간 복잡도 - O(s) - 단일 루프만.
공간 복잡성 - O(s + t) - 해시맵의 경우.

결론

다른 접근 방식을 놓친 경우 알려주십시오.

더 많은 설명을 위해 나를 따르십시오.
연결합시다: Showwcase