1.2 순열확인

문제

문자열 두개가 주어졌을때 이 둘이 서로 순열관계야 있는지 확인하는 메서드를 작성하라

 

1. 정렬하기

 두 문자열이 순열관계라면 문자를 정렬한다음 비교해봤을때 같은 문자열이여야한다. 

def Solution(s1, s2):
    if len(s1) != len(s2):
        return False
    s1.sort()
    s2.sort()
    return s1 == s2

Time Complexity O(NlogN + N)

 

2. 문자열에 포함된 문자의 출연 횟수가 같은지 검사하기

  - Ascii코드라면 128개의 문자들에 대한 배열을 선언하고 각 문자들의 갯수를 세서 비교한다. 

def Solution(s1,s2):
    if len(s1) != len(s2): return False
    
    alpha_cnt = [0]*128
    for c in s1 :
        alpha_cnt[ord(c)] +=1

    for c in s2 :
        alpha_cnt[ord(c)] -=1
        if alpha_cnt[ord(c)] < 0 :
            return False
    return True

Time Complexity O(2N)

 

 

배운점

배열에 숫자를 세서 비교해야겠다는 생각은 했으나 하나의 배열로 비교할 방법을 떠올리지 못했다. 

하나의 배열만을 가지고 첫번째 문자열의 갯수를 구한 다음에 다음 문자열에서 갯수를 빼줌으로써 해결가능