将字符串转换为良好形式的最小递增/递减次数是多少？

Question

我们被要求通过对字符串执行特定的操作来修改它。给定一个由小写英文字母（'a' - 'z'）组成的字符串，可以在任何索引上执行两种类型的操作，任意次数：

1. 将字符减1。字母'a'不能被减少。
2. 将字符加1。字母'z'不能被增加。

计算修改字符串为好的形式所需的最小移动次数。好的形式字符串是每个字符都与至少一个相等字符相邻的字符串。

示例1：

s = ‘aca’

输出：2

解释：将'c'减少两次以得到'aaa'。需要至少2次移动。

示例2：

s = 'abcdef'

输出：3

解释：将'b'减1变为'a'。将'c'加1变为'd'。将'e'加1变为'f'。这样我们得到了"aaddff"。

字符串的第一个和最后一个字符只有一个相邻的邻居，因此它们必须等于该相邻字符。

如何最好地解决这个问题？

我最初认为使用两个指针，一个用于左/起始索引，另一个用于右/结束索引，并将它们缓慢移动到中心可能是最佳方法，使用的思想是字符串的边缘必须等于内部字符才能变得相等。

但这并不能给我们一个全局最优解。最好的方法是否与动态规划有关？如果是，那么它会是什么样子？

- Def Lakos

Answer 1

是的，有一个动态程序可以直接从下面实现的Python算法中提取出来，该算法用于验证解决方案。

def has_good_form(s):
    previous_letter = None
    needs_adjacent_copy = False
    for letter in s:
        if letter == previous_letter:
            needs_adjacent_copy = False
        elif not needs_adjacent_copy:
            previous_letter = letter
            needs_adjacent_copy = True
        else:
            return False
    return not needs_adjacent_copy


print(has_good_form("aca"))
print(has_good_form("aaa"))
print(has_good_form("abcdef"))
print(has_good_form("aaddff"))

has_good_form()函数会记住先前的字母以及是否已知有相邻的副本，总共有26×2=54个状态，再加上初始状态（共55个）。动态规划的思想是，对于每个状态和时间，最便宜的修改集合是什么，可以将has_good_form()函数置于该状态在该时间？具体实现如下（未经测试）。

import collections
import math
import string


def distance(a, b):
    return abs(ord(a) - ord(b))


def cheapest_good_form(s):
    state_to_min_cost = {(None, False): 0}
    for original_letter in s:
        options = collections.defaultdict(list)
        for state, min_cost in state_to_min_cost.items():
            previous_letter, needs_adjacent_copy = state
            for letter in string.ascii_lowercase:
                cost = min_cost + distance(original_letter, letter)
                if letter == previous_letter:
                    options[(letter, False)].append(cost)
                elif not needs_adjacent_copy:
                    options[(letter, True)].append(cost)
        state_to_min_cost = {state: min(costs) for (state, costs) in options.items()}
    return min(
        (
            cost
            for (
                (_, needs_adjacent_copy),
                cost,
            ) in state_to_min_cost.items()
            if not needs_adjacent_copy
        ),
        default=math.inf,
    )


print(cheapest_good_form(""))
print(cheapest_good_form("a"))
print(cheapest_good_form("aca"))
print(cheapest_good_form("abcdef"))

- David Eisenstat