[LeetCode 75] Easy - 345. Reverse Vowels of a String

345. Reverse Vowels of a String

 

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

 

Example 1:

Input: s = "IceCreAm"

Output: "AceCreIm"

Explanation:

The vowels in s are ['I', 'e', 'e', 'A']. On reversing the vowels, s becomes "AceCreIm".

Example 2:

Input: s = "leetcode"

Output: "leotcede"

 

Constraints:

• 1 <= s.length <= 3 * 10^5
• s consist of printable ASCII characters.

 

문제 풀이

 

이 문제는 문자열 s에서 모음만 뒤집어서 새로운 문자열을 반환하는 문제입니다. 모음은 'a', 'e', 'i', 'o', 'u' (소문자와 대문자 모두 포함)로 정의됩니다.

---

문제 조건

1. 문자열 s의 모음만을 찾아서 위치를 유지한 채 뒤집습니다.
2. 모음이 아닌 문자는 그대로 둡니다.
3. 대소문자를 구분하지 않고 모음을 판단합니다.

알고리즘

1. 모음 추출: 문자열 s에서 모음만 골라냅니다.
2. 모음 뒤집기: 추출한 모음을 뒤집습니다.
3. 문자열 생성: s를 순회하면서:
   • 모음이면 뒤집은 모음 배열에서 하나씩 가져와 대체.
   • 모음이 아니면 그대로 유지.
4. 결과 문자열을 반환합니다.

시간 및 공간 복잡도

• 시간 복잡도: O(n)
  • 문자열을 한 번 순회하며 양쪽에서 포인터를 이동하므로 선형 시간.
• 공간 복잡도: O(n)
  • 입력 문자열을 리스트로 변환하므로 추가 공간 필요.

 

https://youtu.be/uHYjUMR3Tg8?si=a4Xz84UtQdO-dmBn

 

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = 'aeiouAEIOU'
        inV = []
        s = list(s)
        for i, w in enumerate(s):
            if w in vowels:
                inV.append((i, w))

        l, r = 0, len(inV)-1
        while(l<r):
            # print(inV[l][0], inV[l][1], s[inV[l][0]])
            # print(inV[r][0], inV[r][1], s[inV[r][0]])
            s[inV[l][0]], s[inV[r][0]] = inV[r][1], inV[l][1]
            l +=1
            r -=1
        print(s)
        return ''.join(s)

 

이걸 최적화해서, Two 포인터로 풀면 정답이 됨

 

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = 'aeiouAEIOU'
        s = list(s)
        l, r = 0, len(s)-1
        while(l<r):
            if s[l] not in vowels:
                l += 1
            elif s[r] not in vowels:
                r -=1
            else:
                s[l], s[r] = s[r], s[l]
                l +=1
                r -=1
            
        return ''.join(s)