Is two-way BFS not supposed to work in this case?-CodePudding

I am solving a problem on LeetCode:

In a string composed of 'L', 'R', and 'X' characters, like "RXXLRXRXL", a move consists of either replacing one occurrence of "XL" with "LX", or replacing one occurrence of "RX" with "XR". Given the starting string start and the ending string end, return True if and only if there exists a sequence of moves to transform one string to the other. Input: start = "RXXLRXRXL", end = "XRLXXRRLX"; Output: true

I solved it using two-way BFS like below:

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;
    }
};

However, for the given input start = "RXXLRXRXL", end = "XRLXXRRLX";, it returns the output false. It follows the below path:

Checking for: XRXLRXRXL
Checking for: RXLXRXRXL
Checking for: RXXLXRRXL
Checking for: RXXLRXXRL
Checking for: RXXLRXRLX
Checking for: XRLXXRRLX
Checking for: RLXXXRRLX

I am not sure why it doesn't consider all the paths and return true. IMO my implementation of two-way BFS is correct.

Is this even solvable by two-way BFS? Am I missing something?

Note: The actual constraints on LeetCode are higher: 1 <= start.length <= 10^4; but for now I am just interested in a two-way BFS implementation (assuming the constraints are 1 <= start.length <= 100 instead).

Thanks!

CodePudding user response：

Debugging: if I comment the "swap first and last" line, the solution works on this test.

The culprit: when considering the actual last instead of first, the program should do inverse operations: not XL to LX and RX to XR, but LX to XL and XR to RX.

Perhaps keep a boolean value (switching whenever you swap first and last) to track which set of operations to use.

The two-way BFS goes forward from the start, and simultaneously backward from the end. As soon as the two searches meet, it has found a path.

To choose in which direction to go, the two-way BFS checks the size of the last layers in both BFS instances, and proceeds with the layer that is smaller.

Naturally, the steps backward from the end have to be reverse steps. The program does not take that into account, and so does not work.