string - 使用BFS将一个字符串转换为另一字符串

有一个字符串的字符只能是“a”、“b”或“$”，该字符串中只有一个“$”。
在每个步骤中，我们可以修改字符串，如下所示：
“$”可以与其相邻字符交换，例如“a$ba”可以更改为“$aba”或“ab$a”。
只有相邻字符与相邻字符不同时，才可以将$character与相邻字符交换（例如，“a b a$a b”可以转换为“a$abab”或“abab$”，但“ab$aab”不能转换为“abaa$b”，因为“a”不能跳过“a”）。
给您两个字符串，初始状态和最终状态（长度将相同），您必须输出将处于初始状态的字符串更改为处于最终状态的字符串所需的最少步骤数。
如何利用广度优先搜索来解决这个问题？
例子：
字符串s1，s2；
输入：s1=a$b，s2=ab$
输出：1
输入：s1=aba$a，s2=$baa
输出：2

最佳答案

这个问题可以通过广度优先搜索来解决，如下所示，使用类似C#的伪代码语法。

string FinalState; (to be assigned the final state)

int DistanceToFinalState(string CurrentState)
{
  if (CurrentState == FinalState)
  {
    return 0; // end of recursion - strings match, distance is zero
  }
  else
  {
    int val1 = Infinity;
    int val2 = Infinity;
    int val3 = Infinity;
    int val4 = Infinity;
    if ($ is not at the leftmost position of CurrentState)
      val1 = DistanceToFinalState(CurrentState with $ moved to the left);
    if ($ is not at the rightmost position of CurrentState)
      val2 = DistanceToFinalState(CurrentState with $ move to the right);
    if ($ has 2 chars left to it)
      val3 = DistanceToFinalState(CurrentState with $ moved 2 chars to the left with the 2 skipped characters reversed);
    if ($ has 2 chars right to it)
      val4 = DistanceToFinalState(CurrentState with $ moved 2 chars to the right with the 2 skipped characters reversed);
    return minumum of {val1, val2, val3, val4};
  }
}

初始问题可以通过计算distancetofinalstate（initialstate）来解决。

关于string - 使用BFS将一个字符串转换为另一字符串，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26347134/