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

Question

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

例子：

• aa（没有变化，只用不同的字符替换）
• bcab > a ab > ac > b （不是 bbb，因为 b 是最短的）
• aba > ca > b
• a（无变化）

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

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 )

标签： pythonalgorithm

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