將一個字符串轉換爲另一個字符串

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，恕我直言。