Question

给定一个字符串s，仅反转字符串中的所有元音并返回它。

元音有“a”、“e”、“i”、“o”和“u”，它们可以以小写和大写形式出现多次。

我的代码可以反转字符串的元音；但是，当输入较大的字符串时，它会因“超出时间限制”而失败。我怎样才能使其更高效，以便能够处理大量输入？

def reverseVowels(self, s: str) -> str:
        v = []
        vowels = ['a', 'e', 'i', 'o', 'u']

        for c in s:
            if c.lower() in vowels:
                v.append(c)

        v.reverse()
        s = list(s)
        j = 0

        for i in range(len(s)):
            if s[i] in v:
                s[i] = v[j]
                j += 1
        s = "".join(s)
                
        return s

示例 2：

输入： s = “leetcode”
输出： “leotcede”

这个例子简直糟透了，因为它没有显示是否只交换e↔ o& a↔ u，或者将第一个元音与最后一个元音交换，将第二个元音与倒数第二个元音交换，…… 那怎么办Y？（代码简直糟透了，因为没有拼写出来……） — 
@greybeard 你为什么问Y？他们写的是“元音是 ‘a’、’e’、’i’、’o’ 和 ‘u’”，这还不够清楚吗？ —

Answer 1

使用时，集合稍快一些in，而理解比使用循环稍快一些append()

enumerate()允许记录元音和元音的索引，确保第二次只迭代元音。

然后，您可以只处理列表的前半部分以及列表的后半部分（反转），交换字符。如果中间元音为奇数，这样做还有一个好处，就是可以跳过中间元音。

vowels = [
    (c, ix)
    for ix, c in enumerate(s)
        if c.lower() in {'a', 'e', 'i', 'o', 'u'}
]

s = list(s)

half = len(vowels) // 2

vowel_pairs = zip(
    vowels[:half]
    vowels[-half:][::-1]
)

for a, b in vowel_pairs:
    s[a[1]] = b[0]
    s[b[1]] = a[0]

s = "".join(s)

演示：

另一种方法是将字符串拆分为交替的部分（辅音、元音、辅音、元音、……、元音、辅音），然后使用切片来反转元音。这会使设置速度变慢，但会将第二个循环移到运行时。trinket.io/python3/ — 
@MatBailie 这就是我的做法（交替部分），不过用的是正则表达式。简单多了。 — 
@nocomment 我对正则表达式很生疏，表达式应该是什么样的？ — 
@nocomment 哇，我本来以为'abba'会是这样['a','bb','a']。我真的应该尝试一下，而不是假设。 —

Answer 2

您可以将其转换vowels为以获得稍微的改进，因为集合比列表可以更快地检查某个值。

对于第二个循环，您不需要再次检查输入的每个字符。由于您已经找到了元音，因此您还可以在第一个循环中存储找到它们的位置：

vowels = set(['a', 'e', 'i', 'o', 'u'])
s_chars = list(s)

vowels_in_s = []
vowel_indexes_in_s = []
for idx, char in enumerate(s_chars):
    if char.lower() in vowels:
        vowels_in_s.append(char)
        vowel_indexes_in_s.append(idx)

然后要将元音添加到其相反的位置，只需反转索引：

vowel_indexes_in_s.reverse()

并使用新的索引替换元音：

for idx, char in zip(vowel_indexes_in_s, vowels_in_s):
    s_chars[idx] = char

是一个很有用的函数，它允许你从单独的列表中构建组合数据结构。这里我们获取一个元音列表和一个索引列表，然后构建[[vowel, index], [vowel, index], ...]。

最后，像之前一样连接角色。将它们全部加在一起，然后：

def reverse_vowels(s):
    vowels = set(['a', 'e', 'i', 'o', 'u'])
    s_chars = list(s)

    vowels_in_s = []
    vowel_indexes_in_s = []
    for idx, char in enumerate(s_chars):
        if char.lower() in vowels:
            vowels_in_s.append(char)
            vowel_indexes_in_s.append(idx)

    vowel_indexes_in_s.reverse()

    for idx, char in zip(vowel_indexes_in_s, vowels_in_s):
        s_chars[idx] = char

    return ''.join(s_chars)

Answer 3

这是你的错误：if s[i] in v:

只需将其更改为if s[i].lower() in vowels:。然后它很容易被接受，我你会这样做。

问题是v可能很大，导致检查很慢。例如对于输入s = 'a'*150000 + 'e'*150000。您的v将是反向的，因此'a'在其中找到每个都需要很长时间，因为搜索会遍历所有这些'e'。您需要二次时间，它应该是线性的。

或者，V = set(v)在循环之间准备并使用if s[i] in V:。

奖励：+切片解决方案（在我的中速度最快，我发现的最快替代方案速度慢约 27%）：

def reverseVowels(self, s: str) -> str:
    a = re.split('([aeiouAEIOU])', s)
    a[1::2] = a[-2::-2]
    return ''.join(a)

是的，我认为二次时间属性是需要修复的最重要的问题；它使代码不可扩展。相比之下，其他一切都微不足道。 —

Answer 4

我立即想到直接循环字符串中的字符，而不是按索引循环，还想测试只添加到字符串而不是转换为列表。阅读其他答案后，我还实现了一个集合，而不是包含大写和小写元音的列表。我不能 100% 确定列表理解是否总是比 for 循环更快，但至少在我看来它看起来更干净。

以下是我的方法：

def reverse_vowels_fast(s: str) -> str:
    # set instead of list with both lower and upper case to omit .lower()
    vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}

    # list comprehension instead of loop
    v = [c for c in s if c in vowels]

    # reverse function instead of slicing
    v.reverse()

    # adding to string instead of converting to and from list
    result = ''

    # looping directly over the string
    for char in s:
        if char in vowels:
            char = v.pop(0)
        result += char

    return result

我将其与@MatBailie 和@no comment 的解决方案进行了比较test_str = 'A slightly longer string to process to see the difference in time better. But only tested manually.'

Function: original_reverse_vowels, execution time: 49700ns
---------
Function: reverse_vowels_no_comment, execution time: 155100ns
Function: reverse_vowels_mat_bailie, execution time: 18100ns
Function: reverse_vowels_fast, execution time: 14400ns

构建这样的结果字符串可能需要二次方的时间。这取决于实现细节。这不是一个好主意，当然不应该被称为“快”。他们可能在 LeetCode 上这样做了，这允许字符串最多包含 300,000 个字符。你为此花了多少时间？用最坏情况的字符串（例如我的示例字符串）进行测量也很好。 — 
从列表中删除的自然位置pop是列表的末尾，而不是前面。.pop(0)将列表中的所有项目向左移动一个位置，因此这是一个缓慢的（O（n））操作。您可以reverse完全跳过调用，只需.pop()（默认为最后一个项目）反转而不反转。此外，添加到字符串也不是一个好主意：字符串是不可变的，因此在指向新字符串之前，创建一个新字符串并将和result += char的内容复制到它。推荐的做法是将附加到列表中，然后执行。resultcharresult''.join(result_list) — 
@Jaime CPython（OP 可能使用过）确实尝试优化字符串扩展，因此它们总体上可能需要线性时间。请参阅和。 —

Answer 5

基准

这很可能来自，所以我在那里对我们的解决方案进行了基准测试。两次尝试：

 76.2 ms  Jan_B
 13.0 ms  MatBailie
 11.9 ms  Simon_Brahan
 21.7 ms  no_comment_minimal_fix_1
 16.0 ms  no_comment_minimal_fix_2
  5.0 ms  no_comment_regex

 76.5 ms  Jan_B
 12.5 ms  MatBailie
 11.6 ms  Simon_Brahan
 21.7 ms  no_comment_minimal_fix_1
 15.9 ms  no_comment_minimal_fix_2
  4.8 ms  no_comment_regex

由于 LeetCode 的时间测量很差，所以我自己做了，在所有 480 个测试用例上运行所有解决方案，并在最后打印总时间。提交的完整代码

class Solution:

    def reverseVowels(self, s: str, timess=[]) -> str:
        from time import perf_counter as time
        funcs = [
            self.no_comment_minimal_fix_1,
            self.no_comment_minimal_fix_2,
            self.no_comment_regex,
            self.Jan_B, 
            self.MatBailie,
            self.Simon_Brahan,
        ]
        names = sorted(f.__name__ for f in funcs)
        
        # Measure each solution on this test case
        times = {f: [] for f in names}
        n = 1
        for _ in range(10):
            shuffle(funcs)
            for f in funcs:
                t = time()
                for _ in range(n):
                    f(s)
                times[f.__name__].append(time() - t)
        timess.append(times)
        
        # Check correctness
        result = funcs[0](s)
        for f in funcs:
            if f(s) != result:
                return None

        # After all test cases, show stats
        if len(timess) == 480:
            for f in names:
                print(f'{sum(min(times[f]) for times in timess) / n * 1e3:5.1f} ms ', f)
            return 'intentionally wrong answer so we get to see the output'

        return result

    
    def no_comment_minimal_fix_1(self, s: str) -> str:
        v = []
        vowels = ['a', 'e', 'i', 'o', 'u']

        for c in s:
            if c.lower() in vowels:
                v.append(c)

        v.reverse()
        s = list(s)
        j = 0

        for i in range(len(s)):
            if s[i].lower() in vowels:
                s[i] = v[j]
                j += 1
        s = "".join(s)
                
        return s

    
    def no_comment_minimal_fix_2(self, s: str) -> str:
        v = []
        vowels = ['a', 'e', 'i', 'o', 'u']

        for c in s:
            if c.lower() in vowels:
                v.append(c)

        v.reverse()
        V = set(v)
        s = list(s)
        j = 0

        for i in range(len(s)):
            if s[i] in V:
                s[i] = v[j]
                j += 1
        s = "".join(s)
                
        return s

    
    def MatBailie(self, s: str) -> str:
        vowels = [
            (c, ix)
            for ix, c in enumerate(s)
                if c.lower() in {'a', 'e', 'i', 'o', 'u'}
        ]

        s = list(s)

        half = len(vowels) // 2

        vowel_pairs = zip(
            vowels[:half],
            vowels[-half:][::-1]
        )

        for a, b in vowel_pairs:
            s[a[1]] = b[0]
            s[b[1]] = a[0]

        return "".join(s)


    def Simon_Brahan(self, s: str) -> str:
        vowels = set(['a', 'e', 'i', 'o', 'u'])
        s_chars = list(s)

        vowels_in_s = []
        vowel_indexes_in_s = []
        for idx, char in enumerate(s_chars):
            if char.lower() in vowels:
                vowels_in_s.append(char)
                vowel_indexes_in_s.append(idx)

        vowel_indexes_in_s.reverse()

        for idx, char in zip(vowel_indexes_in_s, vowels_in_s):
            s_chars[idx] = char

        return ''.join(s_chars)

    
    def no_comment_regex(self, s: str) -> str:
        a = re.split('([aeiouAEIOU])', s)
        a[1::2] = a[-2::-2]
        return ''.join(a)
    
    
    def Jan_B(self, s: str) -> str:
        # set instead of list with both lower and upper case to omit .lower()
        vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'}

        # list comprehension instead of loop
        v = [c for c in s if c in vowels]

        # reverse function instead of slicing
        v.reverse()

        # adding to string instead of converting to and from list
        result = ''

        # looping directly over the string
        for char in s:
            if char in vowels:
                char = v.pop(0)
            result += char

        return result

Answer 6

所呈现的代码的最大问题是它没有它要完成的任务：

看看你的做法和做法如何根据元音序列中的位置进行替换，而其他人的做法则根据字符串中元音的顺序进行替换。

除了使用集合来测试大小写规范化的字符之外，还可以使用包含每个元音的大写和小写的集合。

人们可以建立所使用的元音集，但“替换过程”节省的时间可能比预处理中增加的时间要少。

替代方案：从两侧同时迭代，即时交换元音。

当你到达中间元音时，你就完成了 –

问题：确定你已经到达了中间元音。

建立元音序列及其逆序列，

找到并替换每一个。

你有一个关于如何操作字符串的例子吗？因为字符串在 Python 上是不可变的。 — 
(@MatBailie：想想 Python……但是，在字符串上搜索可能更快，因此在字符串中定位，操作列表。) —

python – 反转字符串中的元音

6 个回答
6

基准

python – 反转字符串中的元音

6 个回答 6

基准

6 个回答
6