345. 反转字符串中的元音字母

发表于 分类于 阅读次数： 本文字数： 192 阅读时长 ≈ 1 分钟

这道题目，我直接想到的就是双指针算法了，一个指针从头往后找，一个指针从后往头找，然后找到元音后停下来，然后，交换，继续循环。

关键是循环终止的位置，应该是头尾两个指针碰到的时候。我就写出了这样的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def reverseVowels(self, s: str) -> str:
        ss = [ x for x in s ]
        i = 0
        l = len(ss)
        j = l - 1
        vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
        while i < j:
            while i < l and ss[i] not in vowels:
                i += 1
            while j > 0 and ss[j] not in vowels:
                j -= 1

            if i <= j:
                ss[i], ss[j] = ss[j], ss[i]
                i += 1
                j -= 1
        return "".join(ss)

我先把字符串转换成了 list，因为我发现字符串里的字符不能更改，记得 Python 的 string 是 immutable 的。所以换了。

这个算法的复杂度理论上是 O(n) 的，不过在尾指针那里，往头部找元音的时候，如果最坏情况，可能会是重复搜索，可以增加一个条件，就是 j >= i 避免无畏地搜索。