[LeetCode] 1704. Determine if String Halves Are Alike

- Problem

1704. Determine if String Halves Are Alike

짝수 길이의 문자열 s가 주어진다. 이 문자열을 반으로 나누고 앞 문자열을 a 뒤 문자열을 b라고 가정하자.
이 때, 두 문자열 모두 같은 수의 모음('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U')을 가지고 있다면 alike 이다.

주어진 문자열이 alike하다면 true, 그렇지 않다면 false를 반환하면 된다.

예제 1번을 보자.
주어진 문자열 s를 반으로 나눈다면 a = "bo", b = "ok" 이다.
a는 모음 o를 1개, b 또한 모음 o를 1개 가지고 있으므로 이 문자열은 alike이다. 따라서, true를 반환한다.

---

- 내 풀이

class Solution:
    def halvesAreAlike(self, s: str) -> bool:
        vowels = set('aeiouAEIOU')
        mid = len(s)//2
        prev_word_vowel_count = 0
        post_word_vowel_count = 0
        
        for i in range(mid):
            if s[i] in vowels:
                prev_word_vowel_count += 1
            
            if s[i+mid] in vowels:
                post_word_vowel_count += 1
        
        return prev_word_vowel_count == post_word_vowel_count

풀이는 간단하다.

• 모음을 식별하기 위한 변수 vowels를 set으로 선언한다.
  - in 연산을 할 때, 시간 복잡도 O(1)을 만족하기 위함이다.

• 문자열의 절반 사이즈 mid를 구하고, 문자열을 순회한다.
  - s[i]는 앞 문자열이다. 만약 s[i]가 vowel일 경우, prev_word_vowel_count를 1 증가 시킨다.
  - s[i+mid]는 뒷 문자열이다. s[i+mid]가 vowel일 경우, post_word_vowel_count를 1 증가 시킨다.

• prev_word_vowel_count와 post_word_vowel_count가 같다면 true를, 그렇지 않다면 false를 리턴한다.

시간 복잡도는 주어진 문자열만큼만 순회하기에 O(N)이라고 볼 수 있다.

---

- 결과

생각해보니, 굳이 vowel count를 두 개 선언 할 필요가 없는 듯하다.

class Solution:
    def halvesAreAlike(self, s: str) -> bool:
        vowels = set('aeiouAEIOU')
        mid = len(s)//2
        vowel_count = 0
        
        for i in range(mid):
            if s[i] in vowels:
                vowel_count += 1
            
            if s[i+mid] in vowels:
                vowel_count -= 1
        
        return vowel_count == 0

앞 문자열이 vowel이라면 1을 더하고, 뒷 문자열이 vowel이라면 1을 빼준다.
vowel_count 가 0이라면 true를 리턴한다.