0345._Reverse_Vowels_of_a_String.md

345. Reverse Vowels of a String

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/reverse-vowels-of-a-string/

内容描述

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:

Input: "hello"
Output: "holle"
Example 2:

Input: "leetcode"
Output: "leotcede"
Note:
The vowels does not include the letter "y".

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

字符串不可变，所以用list代替，最后join, beats 71.26%

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

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

正则版本， beats 79.24%

class Solution:
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """
        vowels = re.findall(r'[aeiouAEIOU]', s)
        return re.sub('[aeiouAEIOU]', lambda m: vowels.pop(), s)

但是Python正则表达式可以直接写成 case insensitive, 在前面加上一个(?i)就可以了, 参考Specifying Modes Inside The Regular Expression

class Solution(object):
    def reverseVowels(self, s):
        """
        :type s: str
        :rtype: str
        """
        vowels = re.findall('(?i)[aeiou]', s)
        return re.sub('(?i)[aeiou]', lambda m: vowels.pop(), s)