345. Reverse Vowels of a String

Leetcode 345번 풀이

문제

Reverse Vowels of a String

풀이

아이디어

투포인터를 이용하는 풀이를 생각했다. 모음의 순서만 뒤집어야 하기 때문에, 양 끝에서부터 모음을 찾아가면서 스왑하는 방식으로 구현했다.

1. 모음 판별을 위한 set을 정의한다. (대소문자 모두 포함) (toLowerCase() 의 호출을 줄일 수 있다. 확실히 실행 속도가 빨라진다.)
2. 투포인터 설정 (양쪽 끝으로 설정한다.)
3. 포인터가 교차할 때까지 아래 과정을 진행한다.
   • 모음이 등장할 때까지 포인터를 이동한다.
   • 스왑이 불가능하다면 종료한다.
   • 모음이 등장했다면 스왑한다.
   • 다음 진행을 위해 포인터를 이동한다.
4. 결과 배열을 문자열로 변환하여 반환한다.

코드

function reverseVowels(s: string): string {
  const ret = [...s];
  // 1. vowels를 판별할 set 정의 (대소문자 모두 포함)
  const vowels = new Set('aeiouAEIOU');
  // 2. 투포인터 설정 (양쪽 끝에서 vowel을 만나면 스왑한다.)
  let left = 0;
  let right = s.length - 1;
  // 3. 진행!
  while (left < right) {
    // a. vowels가 등장할 때 까지 포인터 이동
    while (left < right && !vowels.has(s[left])) left++;
    while (left < right && !vowels.has(s[right])) right--;
    // b. 스왑이 불가능하다면 종료
    if (left >= right) break;
    // c. 스왑
    [ret[left], ret[right]] = [ret[right], ret[left]];
    // d. 다음 진행
    left++;
    right--;
  }
  // 4. 결과 배열 문자열로 변환
  return ret.join('');
}

시간 / 공간 복잡도

• 시간 복잡도: O(n) — 문자열을 양 끝에서 한 번씩 순회
• 공간 복잡도: O(n) — 결과 배열 ret