Remove Vowels

Q: 删除元音的时间复杂度是多少？

一次遍历的时间复杂度是 O(n) ，因为每个字符只需进行一次常数时间的元音检查。最坏情况下，当 s 中完全没有元音时，输出需要 O(n) 的空间。每遇到一个元音就调用一次 replace，时间复杂度也是 O(n) ，但它会读取字符串 10 次。

Q: 你能用正则表达式移除元音吗？

可以。在大多数语言中，将模式 [aeiouAEIOU] 替换为空字符串，一次调用就能完成。它的运行时间是 O(n) ，和循环相同，但面试官通常会让你编写循环，这样他们就能看到你如何检查元音，以及如何构建结果。

Q: 为什么不直接从字符串中删除元音呢？

从中间删除一个字符会让后面的每个字符都向左移动，因此多次删除的时间复杂度可能达到 O(n²) 。你可以用两个索引在原地以 O(n) 的时间复杂度完成，一个索引读取每个字符，另一个索引写入下一个保留的字母。不过，大多数语言中的字符串都无法修改，因此新建一个字符串是更自然的做法。

入门数组和字符串

+10

你会得到一个由英文字母组成的字符串 s。返回删除其中所有元音字母后得到的字符串。元音字母包括小写或大写的 a、e、i、o 和 u；这里 y 不算元音字母。保留下来的字母顺序和大小写都不变。

函数

removeVowels(s: string) → string

sstring: 要清理的英文字母字符串
返回值string: 移除所有元音后的 s，以及按原顺序排列的其他字母

约束条件

1 ≤ s.length ≤ 3 × 10⁴
s 只包含英文字母（a 到 z，A 到 Z）。
s 中至少包含一个非元音字母，因此答案永远不会为空。

示例

输入: s = "Interview"
输出: "ntrvw"
解释: 从 Interview 中删除 I、e、i 和 e 后，会按顺序留下 n、t、r、v、w。大写的 I 也是元音，所以也要删除。

输入: s = "rhythm"
输出: "rhythm"
解释: rhythm 中没有 a、e、i、o 或 u，所以不会删除任何内容。它的 y 不在元音列表中，因此会保留。

输入: s = "EuropeanUnion"
输出: "rpnnn"
解释: EuropeanUnion 的 13 个字母中有 8 个是元音字母，包括大写字母 E 和 U。剩下的 5 个辅音字母 r、p、n、n、n 保持原有顺序，读作 rpnnn。

进阶

如果文本可以包含任意 Unicode 字母，比如 É 或 ö，那会怎样？哪些字母是元音，你的测试又该如何调整？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

从字符串中间逐个删除字符时，每出现一个空隙，后面的所有内容都会移动。改为逐步构建答案：遍历字符串一次，并复制每个非元音字母。正确处理大写元音，并使用构建器拼接结果。

每个元音都单独遍历一遍并删除

思路

大多数语言都可以在一次调用中删除某个字符的所有副本：将它替换为空。对 a e i o u A E I O U 中的每个字符各执行一次。辅音不会被触碰，因此它们的顺序和大小写保持不变。对于 Interview，处理 e、i 和 I 后，结果分别是 Intrviw、Intrvw 和 ntrvw；其他 7 个字符都没有匹配项。

每次处理都会读取整个字符串，总共大约需要 10n 步。这仍然是 O(n)，但对于含有 3 × 10^4 个字母的字符串，需要 3 × 10^5 步，而遍历一次只需要 3 × 10^4 步。

算法

依次处理十个元音字母 aeiouAEIOU。
对于每个字母，将 s 中所有与它相同的字符替换为空。
完成这十轮后，返回 s 中剩下的内容。

def removeVowels(s):
    for vowel in "aeiouAEIOU":
        s = s.replace(vowel, "")  # one full pass for this letter
    return s

保留辅音的一次遍历

思路

保留需要留下的内容，而不是删除不需要的内容。遍历一次 s，并追加每个不属于十个元音字母的字符。按读取顺序追加，且不修改任何字符，因此辅音会保持原有的顺序和大小写。

每个字符只需进行一次常数时间的测试（查询集合、使用 switch，或在包含十个字母的字符串中搜索），因此时间复杂度为 O(n)。追加到构建器或列表中，并在最后一次性将其转换为字符串。输出本身占用 O(n) 的空间。

算法

为结果创建一个空的构建器。
逐个字符遍历 s。
如果字符不是 aeiouAEIOU 中的一个，就将它追加到构建器中。
将构建器作为字符串返回。

def removeVowels(s):
    vowels = set("aeiouAEIOU")
    kept = []
    for ch in s:
        if ch not in vowels:
            kept.append(ch)
    # Joining a list once avoids rebuilding the string on every character.
    return "".join(kept)

易错点和边界情况

忘记了大写元音字母。只检查 aeiou 会把 Interview 变成 Intrvw，而不是 ntrvw。
为了缩短检查过程，把整个字符串都转换成小写。这样 QUEUEING 会变成 qng，而不是 QNG。只把用于检查的副本转换成小写。
按索引向前遍历时删除字符。删除 s[i] 会让下一个字母移到位置 i，而 i++ 会跳过它，所以 aab 会变成 ab。
在循环中用 += 拼接不可变字符串。在 Java 或 C# 中，每一步都会复制整个字符串，对于 3 × 10^4 个字母，大约会复制 4.5 × 10^8 个字符。

常见问题3

删除元音的时间复杂度是多少？

一次遍历的时间复杂度是 O(n)，因为每个字符只需进行一次常数时间的元音检查。最坏情况下，当 s 中完全没有元音时，输出需要 O(n) 的空间。每遇到一个元音就调用一次 replace，时间复杂度也是 O(n)，但它会读取字符串 10 次。

你能用正则表达式移除元音吗？

可以。在大多数语言中，将模式 [aeiouAEIOU] 替换为空字符串，一次调用就能完成。它的运行时间是 O(n)，和循环相同，但面试官通常会让你编写循环，这样他们就能看到你如何检查元音，以及如何构建结果。

为什么不直接从字符串中删除元音呢？

从中间删除一个字符会让后面的每个字符都向左移动，因此多次删除的时间复杂度可能达到 O(n²)。你可以用两个索引在原地以 O(n) 的时间复杂度完成，一个索引读取每个字符，另一个索引写入下一个保留的字母。不过，大多数语言中的字符串都无法修改，因此新建一个字符串是更自然的做法。

def removeVowels(s):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

s = "Interview"

预期输出

"ntrvw"