将字符串更改为相等的字符串

Question

参考问题这里

我们有两个字符串A和B，它们具有相同的字符集。我们需要更改这些字符串以获得两个相等的字符串。在每次移动中，我们可以执行以下操作之一：

1- 交换一个字符串的两个连续字符
2- 交换一个字符串的第一个和最后一个字符

可以对任何一个字符串执行移动操作。我们需要多少次移动才能获得两个相等的字符串？输入格式和约束条件：输入的第一行和第二行包含两个字符串A和B。保证它们的字符集相等。1 <= length(A) = length(B) <= 2000。所有输入字符都在'a'和'z'之间。

看起来这需要使用动态规划来解决。但我无法想出方程式。有人在答案中提出了方程式-但看起来并不完全正确。

dp[i][j] = 
Min{ 
dp[i + 1][j - 1] + 1, if str1[i] = str2[j] && str1[j] = str2[i]
dp[i + 2][j] + 1, if str1[i] = str2[i + 1] && str1[i + 1] = str2[i]
dp[i][j - 2] + 1, if str1[j] = str2[j - 1] && str1[j - 1] = str2[j]
}
In short, it's 
dp[i][j] = Min(dp[i + 1][j - 1], dp[i + 2][j], dp[i][j - 2]) + 1.
Here dp[i][j] means the number of minimum swaps needs to swap str1[i, j] to str2[i, j]. Here str1[i, j] means the substring of str1 starting from pos i to pos j :)

Here is an example like the one in the quesition,
str1 = "aab",
str2 = "baa"

dp[1][1] = 0 since str1[1] == str2[1];
dp[0][2] = str1[0 + 1][2 - 1] + 1 since str1[0] = str2[2] && str1[2] = str2[0].

- Andy897

---

我认为使用DP不可能，至少在这种解决方案中是不可能的，因为您无法将最后一个元素与中间的一个元素交换位置。 - Lrrr

Answer 1

你有两个原子操作：

1. 成本为1的连续交换
2. 成本为1的首尾交换

一个有趣的事实是：

1. 如果将字符串结尾附加到字符串开头（循环字符串），则2和3相同

所以我们可以推导出更通用的操作：

3. 将字符移动，成本= |from - to|（跨越边界）

这个问题对我来说似乎不是二维的，或者我还不能确定维度。将此算法视为天真的方法：

private static int transform(String from, String to) {
    int commonLength = to.length();
    List<Solution> worklist = new ArrayList<>();
    worklist.add(new Solution(0,from));
    while (!worklist.isEmpty()) {
        Solution item = worklist.remove(0);
        if (item.remainder.length() == 0) {
            return item.cost;
        } else {
            int toPosition = commonLength - item.remainder.length();
            char expected = to.charAt(toPosition);
            nextpos : for (int i = 0; i < item.remainder.length(); i++) {
                if (item.remainder.charAt(i) == expected) {
                    Solution nextSolution = item.moveCharToBegin(i, commonLength);
                    for (Solution solution : worklist) {
                        if (solution.remainder.equals(nextSolution.remainder)) {
                            solution.cost = Math.min(solution.cost, nextSolution.cost);
                            continue nextpos;
                        }
                    }
                    worklist.add(nextSolution);
                }
            }
        }
    }
    return Integer.MAX_VALUE;
}

private static class Solution {
    public int cost;
    public String remainder;

    public Solution(int cost, String remainder) {
        this.cost = cost;
        this.remainder = remainder;
    }

    public Solution moveCharToBegin(int i, int length) {
        int costOffset = Math.min(i, length - i); //minimum of forward and backward circular move
        String newRemainder = remainder.substring(0, i) + remainder.substring(i + 1);
        return new Solution(cost + costOffset, newRemainder);
    }
}

- CoronA