리트코드 1657. Determine if Two Strings Are Close

https://leetcode.com/problems/determine-if-two-strings-are-close/?envType=study-plan-v2&envId=leetcode-75

LeetCode - The World's Leading Online Programming Learning Platform

def closeStrings(word1, word2):
    if set(word1) != set(word2): # O(n)
        return False

    word1_count = [0] * 26
    word2_count = [0] * 26
    
    for c in word1: # O(n)
        word1_count[ord(c) - ord('a')] += 1
    for c in word2: # O(n)
        word2_count[ord(c) - ord('a')] += 1

    word1_count.sort() # O(nlogn)
    word2_count.sort() # o(nlogn)

    return word1_count == word2_count

 

먼저 set를 사용하여 두 문자열에 동일한 고유 문자가 포함되어 있는지 확인했다. 동일한 문자를 포함하지 않으면 한 문자열을 다른 문자열로 변환할 수 없기 때문이다.
그런 다음 두 문자열에서 각 문자의 빈도를 계산한다. 여기서는 영어 알파벳의 각 문자에 대해 인덱스가 문자에 해당하는 크기 26의 리스트를 사용했다(인덱스를 찾기 위해 ord(c) - ord('a') 사용).
등장 빈도를 저장한 리스트 정렬했다. 이를 통해 문자를 바꾸고 한 문자의 모든 출현을 다른 문자로 변환할 수 있게 된다. 문자의 순서는 중요하지 않고 빈도만 중요하기 때문에 가능하다.
마지막으로 정렬된 문자 빈도 리스트가 동일한지 확인한다. 동일하다면 주어진 연산을 사용하여 단어1을 단어2로 변환할 수 있다는 뜻이다.

 

시간 복잡도: O(nlogn). 가장 시간이 많이 걸리는 연산은 빈도 배열을 정렬하는 것이다. - python의 sort 메서드는 평균과 최악 모두 nlogn의 시간복잡도를 가진다.
공간 복잡도: O(1). 고정 공간을 사용하므로 상수 공간복잡도를 가진다.