我正在解決 LeetCode 上的一個問題：
在由“L”、“R”和“X”字符組成的字串中，例如“RXXLRXRXL”，移動包括將出現的“XL”替換為“LX”，或者將出現的“RX”替換為“XR”。給定起始字串 start 和結束字串 end，當且僅當存在將一個字串轉換為另一個字串的移動序列時才回傳 True。 輸入：開始=“RXXLRXRXL”，結束=“XRLXXRRLX”；輸出：真
我使用如下所示的雙向 BFS 解決了它：
class Solution {
public:
bool canTransform(string& start, string& end) {
if(start==end) return true;
unordered_set<string> first{start}, last{end}, visited{start,end};
while(first.size() && last.size()) {
if(first.size()>last.size()) swap(first,last);
unordered_set<string> tmp;
for(auto curr:first) {
for(int i=1; i<curr.size(); i ) {
if((curr[i-1]=='X' && curr[i]=='L') || (curr[i-1]=='R' && curr[i]=='X')) {
swap(curr[i-1],curr[i]);
// cout<<"Checking for: "<<curr<<"\n";
if(last.count(curr)) return true;
if(!visited.count(curr)) {
tmp.insert(curr);
visited.insert(curr);
}
swap(curr[i-1],curr[i]);
}
}
}
swap(tmp,first);
}
return false;
}
};
但是，對于給定的輸入start = "RXXLRXRXL", end = "XRLXXRRLX";，它回傳輸出false。它遵循以下路徑：
Checking for: XRXLRXRXL
Checking for: RXLXRXRXL
Checking for: RXXLXRRXL
Checking for: RXXLRXXRL
Checking for: RXXLRXRLX
Checking for: XRLXXRRLX
Checking for: RLXXXRRLX
我不確定為什么它不考慮所有路徑并回傳true。IMO 我對雙向 BFS 的實作是正確的。
這甚至可以通過雙向 BFS 解決嗎？我錯過了什么嗎？
注意：對 LeetCode 的實際約束更高1 <= start.length <= 10^4：但現在我只對雙向 BFS 實作感興趣（假設約束是1 <= start.length <= 100相反的）。
謝謝！
uj5u.com熱心網友回復：
除錯：如果我評論“交換first和last”行，則解決方案適用于此測驗。
罪魁禍首：當考慮實際last而不是 時first，程式應該做逆運算：不是XLtoLX和RXto XR，而是LXtoXL和XRto RX。
也許保留一個布林值（每當您交換first和時切換last）以跟蹤要使用的操作集。
雙向 BFS 從頭向前，同時從尾向后。兩個搜索一相遇，它就找到了一條路徑。
為了選擇前進的方向，雙向 BFS 會檢查兩個 BFS 實體中最后一層的大小，然后繼續處理較小的層。
自然地，從末端向后的步驟必須是反向步驟。該程式沒有考慮到這一點，因此不起作用。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/488649.html
上一篇：無法在陣列之間分配專案