反转字符串中的元音 图解题解

这道题到底在问什么

输入

s="hello"

输出

"holle"（e、o 交换）

输入

s="leetcode"

输出

"leotcede"

最优解：一步一步想明白

1. 3记住「l 找元音、r 找元音、交换、各进一格」，下面每帧都在套它。
2. 4开局:l 指最左、r 指最右。两个指针向中间逼近,各自找元音。
3. 5看 l=0 的 'q',不是元音,l 向右移一格继续找。
4. 6l=1 的 'u' 是元音(红色),l 停下,等右边也找到元音再交换。
5. 7r=11 的 'e' 也是元音(红色)。现在 l、r 两端都停在元音上,可以交换了。
6. 8l、r 都停在元音上了('u' 和 'e',红色),把它们交换。
7. 9交换完成(绿色):'u' 和 'e' 换了位。l、r 各往里走一格,继续找下一对元音。
8. 10l=2 的 'e' 是元音(红色),l 停下,等右边也找到元音再交换。
9. 11看 r=10 的 'l',不是元音,r 向左移一格继续找。
10. 12看 r=9 的 'b',不是元音,r 向左移一格继续找。
11. 13r=8 的 'a' 也是元音(红色)。现在 l、r 两端都停在元音上,可以交换了。
12. 14l、r 都停在元音上了('e' 和 'a',红色),把它们交换。
13. 15交换完成(绿色):'e' 和 'a' 换了位。l、r 各往里走一格,继续找下一对元音。
14. 16看 l=3 的 's',不是元音,l 向右移一格继续找。
15. 17看 l=4 的 't',不是元音,l 向右移一格继续找。
16. 18l=5 的 'i' 是元音(红色),l 停下,等右边也找到元音再交换。
17. 19看 r=7 的 'n',不是元音,r 向左移一格继续找。
18. 20r=6 的 'o' 也是元音(红色)。现在 l、r 两端都停在元音上,可以交换了。
19. 21l、r 都停在元音上了('i' 和 'o',红色),把它们交换。
20. 22交换完成(绿色):'i' 和 'o' 换了位。l、r 各往里走一格,继续找下一对元音。
21. 23l 和 r 相遇,所有元音都首尾对称换好了。最终结果:"qeastoineblu"。非元音字符自始至终没动过。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#include <algorithm>
#include <string>
using namespace std;
class Solution {
public:
    string reverseVowels(string s) {
        string vowels = "aeiouAEIOU";
        auto isV = [&](char c){ return vowels.find(c) != string::npos; };
        int l = 0, r = (int)s.size() - 1;
        while (l < r) {
            while (l < r && !isV(s[l])) l++;
            while (l < r && !isV(s[r])) r--;
            swap(s[l++], s[r--]);
        }
        return s;
    }
};

import java.util.*;
class Solution {
    public String reverseVowels(String s) {
        Set<Character> vowels = new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
        char[] arr = s.toCharArray();
        int l = 0, r = arr.length - 1;
        while (l < r) {
            while (l < r && !vowels.contains(arr[l])) l++;
            while (l < r && !vowels.contains(arr[r])) r--;
            char tmp = arr[l]; arr[l++] = arr[r]; arr[r--] = tmp;
        }
        return new String(arr);
    }
}

复杂度

面试官可能追问