algorithm - 找到转换为回文的最小成本

Question

我被这个问题困了很久，一直找不到有效的解决办法。任何帮助将不胜感激。

问题:

给定一个包含小写字符的字符串，我们需要找到将其转换为回文的最小成本。我们可以插入新字符并删除现有字符。每个字符都有一个与之相关的插入和删除成本。

成本是 'a' = 1, 'b' = 2, 'c' = 3,....., 'z' = 26

例如'abc' -> 'c' 成本为 3

我只能想到一种方法，该方法涉及遍历所有具有指数时间复杂度的子序列。 有什么办法可以优化它吗？

Answer 1

你可以想象一个递归的解决方案，你解决使第一个和最后一个字符相同的问题，然后解决剩余字符(不包括第一个和最后一个字符)的问题。

如果字符串的第一个和最后一个字符已经相同，考虑在字符串的开头或结尾插入一个字符，也没有删除第一个或最后一个字符的意义。这只会增加成本。

当不同时，有几个选项可以让第一个字符与最后一个字符相同:

1. 在开头插入一个字符:与当前字符串的最后一个字符相同的字符。该字符的成本应添加到递归将为没有最后一个字符的原始字符串提供的成本中。

2. 在最后插入一个字符:与当前字符串的第一个字符相同的字符。该字符的成本应添加到递归将为没有第一个字符的原始字符串提供的成本中。

3. 删除最后的字符:这可能不会立即使第一个和最后一个字符相等，因为可能需要删除/插入更多字符。但是这个选择将是递归调用的工作。该字符的成本应添加到递归将为剩余字符串提供的成本中。

4. 删除最开始的字符(与选项 3 相同的推理):应该将此字符的成本添加到递归将为剩余字符串提供的成本中。

观察选项1和选项3的递归调用是一样的，而且增加的代价也是完全一样的。比较选项 2 和 4 时也有类似的观察结果。例如，当输入为“abcb”时，我们可以看到在末尾添加“a”或从开头删除“a”，两者都会产生相同的回文成本。所以实际上我们只需要考虑这 4 个选项中的 2 个。

在对这两个选项进行递归调用之后，唯一剩下的就是选择两者中最便宜的一个。

当只剩下 1 个字符(或没有)时，递归停止:对于这种情况，成本为 0，因为该字符串是回文。该(零)成本甚至相应的回文都可以返回给调用者。

通过内存可以进行一些优化:跟踪每个访问范围的结果。

下面是一个 JavaScript 实现，它有一个交互式输入，您可以在其中实时看到相应的计算成本和回文:

function toPalindrome(s, charCost) {
    let visited = [];
    function recur(i, j) {
        let key = i * s.length + j;
        if (visited[key]) return visited[key];  // use memoization
        let cost = 0, palindrome;
        if (i >= j) { // Base case
            palindrome = i > j ? "" : s[i];
        } else if (s[i] === s[j]) {
            // If outermost two characters are equal: take them; no extra cost
            ({ cost, palindrome } = recur(i+1, j-1));
            palindrome = s[i] + palindrome + s[i];
        } else { // Otherwise consider deleting either first or last char
            ({ cost, palindrome } = recur(i, j-1));
            cost += charCost[s[j]];
            let { cost: cost2, palindrome: palindrome2 } = recur(i+1, j);
            cost2 += charCost[s[i]];
            if (cost2 < cost) { // Take best of the two searched branches
                cost = cost2;
                palindrome = palindrome2;
            }
        }
        // Return two informations: cost and palindrome.
        return visited[key] = { cost, palindrome };
    }
    return recur(0, s.length-1);
}

const charCost = [...Array(26).keys()].reduce((acc, i) => 
    (acc[String.fromCharCode(i+97)] = i+1, acc), {});
// I/O handling
(document.oninput = () =>
    output.textContent = JSON.stringify(toPalindrome(input.value, charCost), null, 2)
)();

Input: <input id="input" value="antenna"><br>
<pre id="output"></pre>

返回所有回文

由于在一端删除一个字符与在另一端添加该字符的成本相同，因此可以以相同的最小成本创建多个回文。

这是一个收集所有这些回文而不是一个回文的代码版本。显然，这使用了一些额外的执行时间和空间:

function toPalindrome(s, charCost) {
    let visited = [];
    function recur(i, j) {
        let key = i * s.length + j;
        if (visited[key]) return visited[key];  // use memoization
        let cost = 0, palindromes;
        if (i >= j) { // Base case
            palindromes = [i > j ? "" : s[i]];
        } else if (s[i] === s[j]) {
            // If outermost two characters are equal: take them; no extra cost
            ({ cost, palindromes } = recur(i+1, j-1));
            palindromes = palindromes.map(pal => s[i] + pal + s[i]);
        } else { // Otherwise consider deleting either first or last char
            ({ cost, palindromes } = recur(i, j-1));
            // add an alternative for every palindrome: using an insertion instead of deletion
            //    at the opposite end of the string
            palindromes = [...palindromes, ...palindromes.map(pal => s[j] + pal + s[j])];
            cost += charCost[s[j]];
            let { cost: cost2, palindromes: palindromes2 } = recur(i+1, j);
            cost2 += charCost[s[i]];
            if (cost2 <= cost) { // Take best of the two searched branches
                if (cost2 < cost) {
                    palindromes = [];
                }
                palindromes = [...palindromes, ...palindromes2, ...palindromes2.map(pal => s[i] + pal + s[i])];
                cost = cost2;
            } 
        }
        // Return two informations: cost and palindrome.
        return visited[key] = { cost, palindromes };
    }
    let result = recur(0, s.length-1);
    result.palindromes = [...new Set(result.palindromes)]; // make unique
    return result;
}

const charCost = [...Array(26).keys()].reduce((acc, i) => 
    (acc[String.fromCharCode(i+97)] = i+1, acc), {});
// I/O handling
(document.oninput = () =>
    output.textContent = JSON.stringify(toPalindrome(input.value, charCost), null, 2)
)();

Input: <input id="input" value="antenna"><br>
<pre id="output"></pre>