找到转换为回文的最低成本

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种。

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

当只剩下一个字符(或一个字符都没有)时，递归就停止了:对于这种情况，成本是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>

​

Answer 2

enum Action { Initial, Unchanged, Insert, Delete }

int defaultEditCost(char ch) => char.ToLower(ch) - 'a' + 1;

int editDistancePalindrime(string str, Func<char, int> costFn)
{
    // Calculate the levenshtein distance table between `str` and its reverse.
    // str[i-1] is the normal string, and str[n-j] is the reverse.
    int n = str.Length;
    var table = new (Action action, int totalCost, int actionCost)[n + 1, n + 1];
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (i == 0 && j == 0) table[i, j] = (Action.Initial, 0, 0);
            else if (i == 0)
            {
                var insertCost = costFn(str[n - j]);
                var insertTotalCost = table[i, j - 1].totalCost + insertCost;
                table[i, j] = (Action.Insert, insertTotalCost, insertCost);
            }
            else if (j == 0)
            {
                var deleteCost = costFn(str[i - 1]);
                var deleteTotalCost = table[i - 1, j].totalCost + deleteCost;
                table[i, j] = (Action.Delete, deleteTotalCost, deleteCost);
            }
            else if (str[i - 1] == str[n - j])
            {
                table[i, j] = (Action.Unchanged, table[i - 1, j - 1].totalCost, 0);
            }
            else
            {
                var insertCost = costFn(str[n - j]);
                var deleteCost = costFn(str[i - 1]);
                var insertTotalCost = table[i, j - 1].totalCost + insertCost;
                var deleteTotalCost = table[i - 1, j].totalCost + deleteCost;
                if (insertTotalCost <= deleteTotalCost)
                {
                    table[i, j] = (Action.Insert, insertTotalCost, insertCost);
                }
                else
                {
                    table[i, j] = (Action.Delete, deleteTotalCost, deleteCost);
                }
            }
        }
    }
    // The cost is the sum of actionCost for all inserts or all deletes.
    // (Both have the same value, because of symmetry.)
    int palindromeCost = 0;
    for (int i = n, j = n; i > 0 || j > 0;)
    {
        var (action, totalCost, actionCost) = table[i, j];
        switch (action)
        {
            case Action.Insert:
                palindromeCost += actionCost;
                j--;
                break;
            case Action.Delete:
                i--;
                break;
            case Action.Unchanged:
                i--;
                j--;
                break;
        }
    }
    return palindromeCost;
}

void Main()
{
    editDistancePalindrime("abc", defaultEditCost).Dump();
    // 'abc' -> 'c' or 'abcba' (cost 3)

    editDistancePalindrime("anchitjain", defaultEditCost).Dump();
    // 'anchitjain' -> 'nitin' or 'anchiajtjaihcna' (cost 23)
}