Leetcode 242. 유효한 아나그램. DSA # 5

질문 링크

쉬운

Python

이 질문에서 우리는 두 문자열이 서로의 애너그램인지 아닌지를 확인해야 합니다.
두 문자열이 동일한 문자를 가지고 있는지 확인해야 함을 의미합니다.

이제 어떻게 확인할 수 있습니까?

두 문자열을 정렬한 다음 비교할 수 있습니다.

예: s = "anagram", t = "nagaram"
정렬 후: s = "aagmnr", t = "aagmnr"
이제 두 문자열을 비교할 수 있습니다.

그러나이 접근 방식은 O(nlogn) 시간 복잡성이 필요합니다. 그리고 우리는 그것을 원하지 않습니다

다음과 같이 생각할 수 있습니다.

영어에는 26개의 알파벳이 있습니다.

따라서 문자열의 각 문자는 26개의 알파벳 중 하나일 수 있습니다.

따라서 크기가 26인 배열을 만들고 각 문자의 수를 배열에 저장할 수 있습니다.

주어진 문자열의 개수를 배열에 저장할 수 있습니다.

그리고 다른 문자열을 확인합니다. 배열에서 0을 만나면 이것이 새 문자라는 의미이므로 False를 반환할 수 있습니다.

예를 들어 이해해 봅시다.

s = "anagram", t = "nagaram"

 storage = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 - We iterate over the string s and store the count of each character in the array.
    - s = "anagram"
     ---------------------------
     1. a -> storage[0] = 1
     2. n -> storage[13] = 1
     3. a -> storage[0] = 2
     4. g -> storage[6] = 1
     5. r -> storage[17] = 1
     6. a -> storage[0] = 3
     7. m -> storage[12] = 1
     ---------------------------

 storage = [3, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0] 

 Now we iterate over the string t and check if we encounter 0 or not
 If we encounter 0 then that means that this character is not present in the string s.

    - t = "nagaram"
     ---------------------------
     1. n -> storage[13] = 1  Since n is present we subtract 1 from storage[13] = 0
     2. a -> storage[0] = 3   Since a is present we subtract 1 from storage[0] = 2
     3. g -> storage[6] = 1   Since g is present we subtract 1 from storage[6] = 0
     4. a -> storage[0] = 2   Since a is present we subtract 1 from storage[0] = 1
     5. r -> storage[17] = 1  Since r is present we subtract 1 from storage[17] = 0
     6. a -> storage[0] = 1   Since a is present we subtract 1 from storage[0] = 0
     7. m -> storage[12] = 1  Since m is present we subtract 1 from storage[12] = 0      
     ---------------------------     

     Since we don't encounter 0 in the array, we can return True.

     Let's take another example:

     s = "abbcc", t = "abbccc"

        storage = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

        - s = "abbcc"
         ---------------------------
         1. a -> storage[0] = 1
         2. b -> storage[1] = 1
         3. b -> storage[1] = 2
         4. c -> storage[2] = 1
         5. c -> storage[2] = 2
         ---------------------------

        storage = [1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

        - t = "abbccc"
         ----------------
            1. a -> storage[0] = 1  Since a is present we subtract 1 from storage[0] = 0
            2. b -> storage[1] = 2  Since b is present we subtract 1 from storage[1] = 1
            3. b -> storage[1] = 1  Since b is present we subtract 1 from storage[1] = 0
            4. c -> storage[2] = 2  Since c is present we subtract 1 from storage[2] = 1
            5. c -> storage[2] = 1  Since c is present we subtract 1 from storage[2] = 0
            6. c -> storage[2] = 0  Sice we encounter 0 in the array, we can return False.

            ---------------------------

구현해 봅시다:

def isAnagram(s: str, t: str) -> bool:
    s_length, t_length = len(s), len(t)
    if s_length != t_length:
        return False

    storage = [0] * 26

    for char in s:
        storage[ord(char) - ord('a')] += 1

    for char in t:
        if storage[ord(char) - ord('a')] == 0:
            return False
        storage[ord(char) - ord('a')] -= 1

    return True

시간 복잡도: O(n)
공간 복잡도: O(26) = O(1)

크기가 26인 배열을 사용하는 대신 사전을 사용하여 각 문자의 수를 저장할 수 있습니다.

def isAnagram(self, s: str, t: str) -> bool:
    s_length, t_length = len(s), len(t)
    if s_length != t_length:
        return False

    storage = {}

    for char in s:
        storage[char] = storage.get(char, 0) + 1

    for char in t:
        if char not in storage or storage[char] == 0:
            return False
        storage[char] -= 1

    return True