Permutation in String [leetcode]

문제

문제 풀이

문자열의 퍼뮤테이션 이 존재하는지 여부 판단 문제이다.

문자열의 퍼뮤테이션은 문자열의 길이가 길어질수록 연산량이 급격히 증가하기 때문에

다른 식으로 풀었는데 바로 dictionary (다른말로 Map) 이다.

 

순서만 바뀐 문자열의 경우, 사용된 문자와 해당 문자 개수가 같다는 점을 이용해

{ “a” : n개, “b” : m개, ...} 등으로 나타내

• 같은 키 값을 가지고 있는지, 서로 다른 키가 존재하지 않는지 여부
• 같은 키 값에 대해 동일한 수량을 가지고 있는지 여부

를 검사하면 퍼뮤테이션 연산을 피할 수 있다.

코드상으로는

1. dictionary를 만드는 함수
2. dictionary 2개를 서로 비교하는 함수

를 구성했다.

#dictionary를 만드는 함수
def dictCreate(self, s):
    temp_dict = {}
    for n in s:
        if n in temp_dict:
            temp_dict[n] += 1
        else:
            temp_dict[n] = 1
    return temp_dict

#dictionary 2개를 서로 비교하는 함수
def dictCompare(self, dict1, dict2):
		# 같은 key값을 가지고 있는지, 다른 key값이 없는지
    if len(set(dict1.keys()) - set(dict2.keys())) == 0 and len(set(dict2.keys()) - set(dict1.keys())) == 0:
        for key in dict1.keys():
            if dict1[key] != dict2[key]:
                return False
        return True
    else:
        return False

 

해당 함수를 통해 메인 함수를 구성하는데

비교 당할 문자열 (이하 s2) 에서 비교할 문자열 (이하 s1) 의 dictionary key값 들중 하나가 등장한다면, 해당 위치에서 s1의 길이만큼만 떼서 dictionary를 만든 뒤, 두 dictionary 값을 비교해보자.

s1_dict = self.dictCreate(s1) # s1을 dictionary 로 변환
for i in range(len(s2)):
    alpha = s2[i] # 한글자씩 확인하기 위해!
    if alpha in s1: # 만약 s1에 포함된 문자라면
        s2_dict = self.dictCreate(s2[i:i+len(s1)]) #s1의 길이만큼 떼와서 dictionary 변환
        if self.dictCompare(s1_dict, s2_dict): # 비교해서 같다면 
            return True # True 반환

로직 상 문제는 없다. 하지만

통과는 했지만, 시간이 오래걸린다고 나온다...

 

 

두번째 시도로는 한글자씩 전부 볼 필요가 있을까? 등장하는 문자열 위치만 확인하면 되지 않을까?

싶어서 코드를 고쳤다.

s1_dict = self.dictCreate(s1)
        
index_list = [] # s1 문자가 등장하는 s2 위치를 저장하는 리스트 생성 
for key in s1_dict.keys(): # s1 문자를 순회
		# s2를 돌면서 해당 문자가 등장하는 위치값을 index_list에 저장
    index_list.extend([i for i in range(len(s2)) if s2.startswith(key, i)])

그럼 위치 리스트만 순회하면서 검사하면 되니까 s2를 전부 보는 것보다 시간이 쪼끔이라도 절약되지 않을까?

그렇다. 통과다. 하지만 여전히 속도는 처참...

하지만 통과됐으니 오늘은 여기까지~

 

전체 코드

class Solution:
    def dictCreate(self, s):
        temp_dict = {}
        for n in s:
            if n in temp_dict:
                temp_dict[n] += 1
            else:
                temp_dict[n] = 1
        return temp_dict
    
    def dictCompare(self, dict1, dict2):
        if len(set(dict1.keys()) - set(dict2.keys())) == 0 and len(set(dict2.keys()) - set(dict1.keys())) == 0:
            for key in dict1.keys():
                if dict1[key] != dict2[key]:
                    return False
            return True
        else:
            return False
        
    def checkInclusion(self, s1: str, s2: str) -> bool:
        
        s1_dict = self.dictCreate(s1)
        
        index_list = []
        for key in s1_dict.keys():
            index_list.extend([i for i in range(len(s2)) if s2.startswith(key, i)])
            
        for i in index_list:
            alpha = s2[i]
            if alpha in s1:
                s2_dict = self.dictCreate(s2[i:i+len(s1)])
                if self.dictCompare(s1_dict, s2_dict):
                    return True
        return False