将一个字符串转换为另一个字符串

Question

有一个字符串，其字符只能是a,b或_，字符串中只有一个_。

在每一步中，我们可以修改字符串如下：

_可与其相邻的字符被交换，例如a_ba可以改变为任一_aba或ab_a。

您可以把_字符与旁边相​​邻字符只有当相邻的字符是从旁边相邻的性格不同。 （例如aba_ab可以转换为a_abab或ababa_，但ab_aab不能转换为abaa_b，因为a不能跳过a）。

给出两个字符串，初始状态和最终状态（长度相同），必须输出将初始状态的字符串更改为最终状态字符串所需的最小步数。

例如：

string s1 ,s2 ; 
input: s1 = a_b , s2 = ab_ 
output: 1 
input: s1 = aba_a , s2 = _baaa 
output: 2 

Answer 1

这可以当你想到这个问题作为一个图形问题很简单地加以解决。

顶点是所有可能的状态，并且有一个边从两个顶点，如果你可以从一个到另一个使用一个单一的举动得到。
现在的问题是在此图中找到从源到目的地的最短路径。

您的代码基本上是实现这个图的DFS，但DFS是不是最佳的。您应该尝试实施BFS，该保证是最优的（始终找到最短路径）。

更复杂的优化（更快的运行时间），包括A *搜索算法和双向搜索，但你现在应该避免这些并专注于简单的BFS，恕我直言。