试图减少 python leetcode 问题中的运行时间

Question

编辑：因为我不清楚我只是要复制问题（我的答案是代码）。

给定一个字符串，通过交换相邻的 'a' 和 'b' 字符或相邻的 'b' 和 'c' 字符任意次数，获得按字母顺序排列的最小字符串。

示例： s = "abaacbac" 通过应用以下操作获得按字母顺序排列的最小可能字符串：

'c' 广告索引 5 与 'b' 广告索引 6 交换，因此“abaacbac”变为“abaabcac”。

然后索引 2 处的 'b' 与索引 3 处的 'a' 交换，因此 'abaabcac' 变为“aababac”。

最后，索引 3 的 'b' 与索引 4 的 'a' 交换以获得最终答案“aaabbcac”。

另一个例子：输入 baacba 输出 aabbca

这是我的代码

def smallestString(s):
    # Write your code here
    cons = 10 ** 5
    if len(s) > cons:
        return False
    s = list(s)
    counter = 0
    while counter < len(s):
        for i in range(len(s)):
            if i + 1 < len(s):
                if s[i] == "b" and s[i + 1] == "a":
                    s[i], s[i + 1] = s[i + 1], s[i]
                elif s[i] == "a" and s[i + 1] == "b" and "c" in s[:i]:
                    s[i + 1], s[i] = s[i], s[i + 1]

                elif s[i] == "c" and s[i + 1] == "b":
                    s[i], s[i + 1] = s[i + 1], s[i]

        counter += 1
    return ''.join(s)

我是否优化了我的代码，使其适用于非常大的输入（最多 10 秒或超时）。 ps 任何不同的建议 approach/modification 也很好

Answer 1

因为我不太清楚你要在这里做什么，我需要指出你有两个循环 while counter < len(s): 和 for i in range(len(s)): 是完全一样的。所以基本上你在 for 循环中执行 len(s) 次的“逻辑位”。这可能一直是你的意图，但似乎是一种奇怪的方式来继续它。取而代之的是删除 while 循环和 counter 变量，看看你是否得到了想要的结果。

否则可能会修改代码，以便您可以在一个循环中完成所有操作（例如 for i in range(len(s) ** 2)。另外，第一个 if i + 1 < len(s) 语句是不必要的，可以作为 for 循环声明的一部分（range(len(s) - 1))

Answer 2

我假设 a、b 和 c 是唯一的字符（我会在最后对此进行评论）。

本质上，b可以自由移动，但是a和c不能相对移动。因此，一个简单的线性时间解决方案是删除所有 bs，而是将它们放在 as 之后但在第一个 c（如果有的话）之前。

以你的例子为例： abaacbac → aaacac → aaabbcac

两种实现方式：

import re

def smallestString(s):
    bs = 'b' * s.count('b')
    s = s.replace('b', '')
    return re.sub('(?=c|$)', bs, s, count=1)

def smallestString(s):
    bs = 'b' * s.count('b')
    s = s.replace('b', '')
    c = s.find('c')
    return s + bs if c < 0 else s[:c] + bs + s[c:]

对于长度为 1000 的随机字符串，我得到这样的时间：

542.781 ms  yours
  0.038 ms  my regex-solution
  0.022 ms  my find-solution

随机可能对你来说甚至不是最坏的情况，我得再考虑一下。

关于我假设该字符串仅包含 a、b 和 c 字符：您的任务描述使它看起来像那样，并且可能由实际规范保证LeetCode，因为允许其他字符只会让它变得更丑，而不是更难或更有趣。您只需找到 a/b/c 个字符的条纹并解决每个这样的条纹。

试图减少 python leetcode 问题中的运行时间

trying to reduce runtime in python leetcode question

python

arrays

sorting

reduce

runtime