[leetcode] 777. Swap Adjacent in LR String

Description

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.

Example:

Input:

start = "RXXLRXRXL", end = "XRLXXRRLX"      

Output:

True      

Explanation:

We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX      

Note:

1. 1 <= len(start) = len(end) <= 10000.
2. Both start and end will only consist of characters in {‘L’, ‘R’, ‘X’}.

分析

• 不論是L還是R，其隻能跟X交換位置，L和R之間是不能改變相對順序的，是以如果分别将start和end中所有的X去掉後的字元串不相等的話，那麼就永遠無法讓start和end相等了。
• 這個判斷完之後，就來驗證L隻能前移，R隻能後移這個限制條件吧，當i指向start中的L時，那麼j指向end中的L必須要在前面，是以如果i小于j的話，就不對了，同理，當i指向start中的R，那麼j指向end中的R必須在後面，是以i大于j就是錯的，最後别忘了i和j同時要自增1，不然死循環了。

代碼

class Solution {
public:
    bool canTransform(string start, string end) {
        int i=0,j=0;
        int n=start.size();
        while(i<n&&j<n){
            while(i<n&&start[i]=='X') ++i;
            while(j<n&&end[j]=='X') ++j;
            if(start[i]!=end[j]) return false;
            if((i<j&&start[i]=='L')||(i>j&&start[i]=='R')){
                return false;
            }
            i++;
            j++;
        }
        return true;
    }
};      

參考文獻