2021-01-22] Determine if Two Strings Are Close

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/582/week-4-january-22nd-january-28th/3613/

 

오늘은 금요일!! 불금이지만 문제풀이로 오늘을 불태운다면 발전하는 나를 볼수있을것이다..

 

이번 문제에서 주어진 Operation 2개에 대해서 이야기를 하자.

입력값으로 주어지는 2개의 문자열에서 하나의 문자열을 Operation 1,2를 사용하여 동일하게 만들 수 있으면

두 문자열은 가깝다고 생각하고 가까우면 True, 문자열이 동일해지지 않으면 False 를 반환하는 문제이다.

Operation 1: 문자열에서 두 문자를 위치 변경이 가능하다. ( b -> e / e -> b )

Operation 2: 동일한 문자가 있으면 그것까지 전부 바뀌는 문자로 변환 ( aaa -> bbb / bb -> aa )

 

예시 1) 'abc' / 'bca' abc를 문자 순서를 두번 바꾸면 bca가 되므로 두 문자열은 가까워 반환값은 True

예시 2) 'a' / 'aa' a를 operation 1,2로 뭘 해봐도 aa가 될수 없다.

예시 3) 'cabbba' / 'abbccc' 문자 순서를 한번 바꾸고, 여러개 바꾸는 방법으로 변경하면 가까워질 수 있다.

예시 4) 'cabbba' / 'aabbss' 문자열이 가진 문자의 종류가 다르므로, 'ss'를 첫번째 문자열이 가질 수 없어 False

 

알게된 실패조건들은 다음과 같다.

 1) 주어진 문자열 두개의 길이가 다르면 무조건 False

 2) 주어진 문자열에 존재하는 문자 종류 및 문자의 개수가 다르면 False

      즉 , 'aaabbb' / 'bababa' 를 분석해보면 두 문자열 모두  a: 3, b: 3 으로 구성되어 operation 1로 동일하게 가능

      'aabbccc' / 'ccaabbb'는 a:2, b:2, c:3 / c:2, a:2, b:3 으로 다른 것 처럼 보이지만, operation1, 2를 적절히 쓰면 가능

      'aaabccc' / 'aabbcc'는 a:3, b:1, c:3 / a:2, b:2, c:2 으로 종류는 같지만 개수가 달라 불가능

 

나는 많은 memory를 사용하고, sort가 많아 runtime도 길긴했지만, 아래와 같이 짤 수 있었다.

 

문제풀이)

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        if len(word1)!=len(word2): # 종단조건 1 : 두 문자열의 길이가 다르면 False
            return False
        w1dict=dict()
        w2dict=dict()
        for i in range(len(word1)): # 두 문자열이 같으로 for문은 하나만 사용
            d1=word1[i]
            d2=word2[i]
            if d1 in w1dict:
                w1dict.update({d1:w1dict[d1]+1}) # dictionary로 문자가 몇번나왔는지 저장
            else:
                w1dict[d1]=1
            if d2 in w2dict:
                w2dict.update({d2:w2dict[d2]+1})
            else:
                w2dict[d2]=1
        w1keys=sorted(list(w1dict.keys())) # 각 저장한 word들의 keys와 values를 정렬하여 저장
        w2keys=sorted(list(w2dict.keys()))
        w1list=sorted(list(w1dict.values()))
        w2list=sorted(list(w2dict.values()))
        #print(w1list,w2list)
        if w1list==w2list and w1keys==w2keys: # 이 정렬된 내용이 둘다 같다면 True
            return True
        return False