0345._reverse_vowels_of_a_string.md

Navigation

• Navigation
• Links
• Solution 1 双指针

Links

1. https://leetcode.com/problems/reverse-vowels-of-a-string/
2. https://leetcode-cn.com/problems/reverse-vowels-of-a-string/

Solution 1 双指针

    时间复杂度：O(N)
    空间复杂度：O(N)。因为要转换成list。'str' object does not support item assignmen.

class Solution:
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """
        arr = list(s)
        # vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
        vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'} # 集合底层是hashtable，所以比较快。in 操作符，set为O(1)，list为O(N)。
        left, right = 0, len(arr) - 1

        while left < right:
            while arr[left] not in vowels and left < right:
                left += 1
            
            while arr[right] not in vowels and left < right:
                right -= 1

            if left < right:
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
                right -= 1

        return ''.join(arr)