python - 在不使用嵌套 for 循环的情况下替换字符的最佳算法是什么？

Question

假设我将有一个由 3 个字母“a”、“b”、“c”组成的字符串，我需要通过用第三个字符替换每两个字符来缩短字符串。最好的方法是什么？

例子:

• aa(没有变化，只是用不同的字符进行了替换)
• bcab > a ab > a c > b(不是 bbb，因为 b 是最短的)
• aba > ca > b
• 一个(没有变化)

我做了以下，但我想有更好的解决方案或算法:

def replaceChar(input_string):  
     possibilites = {'ab':'c',
                     'bc':'a', 
                     'ca':'b',
                     'cb':'a', 
                     'ac':'b', 
                     'ba':'c'
                     }
     for key, value in possibilites.items():
          input_string = input_string.replace(key, value)
          char_game(input_string)

def char_game(input_string):
        if len( list(set(input_string)) ) == 1: print(input_string)
        elif len( list(set(input_string)) ) >= 2 : replaceChar(input_string)
        else: print( input_string )

Answer 1

同意@gene 的观点，您的解决方案可能无法提供最佳解决方案。但是，如果您想采用您的方法，那么使用附加堆栈的 O(N) 解决方案可能会成功

def getchar(input_string):
    rep = {
        'ab':'c',
        'bc':'a',
        'ca':'b',
        'cb':'a',
        'ac':'b',
        'ba':'c'
    }
    stack = []
    for c in input_string:
        t = c
        while len(stack) and stack[-1] != t:
            t = rep[t+stack[-1]]
            stack.pop()
        stack.append(t)
    return stack