leetcode,腦筋急轉彎，字元串

題目

在一個由 ‘L’ , ‘R’ 和 ‘X’ 三個字元組成的字元串（例如"RXXLRXRXL"）中進行移動操作。一次移動操作指用一個"LX"替換一個"XL"，或者用一個"XR"替換一個"RX"。現給定起始字元串start和結束字元串end，請編寫代碼，當且僅當存在一系列移動操作使得start可以轉換成end時， 傳回True。

示例 :

輸入: start = "RXXLRXRXL", end = "XRLXXRRLX"
輸出: True
解釋:
我們可以通過以下幾步将start轉換成end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX
           

注意:

1 <= len(start) = len(end) <= 10000。
start和end中的字元串僅限于'L', 'R'和'X'。

           

我的第一次做法much wrong

//2018/12/24
class Solution {
public:
    bool canTransform(string start, string end) 
    {
        if(start.size() != end.size())
            return false;
        for(int i = 0; i < start.size(); i++)
        {
            if(start[i] == end[i])
                continue;
            if(end[i] == 'X')
            {
                if(start[i] == 'L')
                    return false;
                else
                    if((i < start.size() - 1) && (start[i+1] == 'X'))
                       {
                           swap(start[i],start[i+1]);
                           continue;
                       }
                    else return false;       
            }
            if(end[i] == 'L')
            {
                if(start[i] == 'R')
                    return false;
                else
                {
                    int j = i + 1;
                    while(j < start.size())
                    {
                        if(start[j] == 'X')
                            j++;
                        else break;
                    }
                    if( (j < start.size()) && (start[j] == 'L') )
                    {
                        swap(start[i],start[j]);
                        continue;
                    }
                    else return false;    
                }
            }  
            return true;   //wrong        
        }
    }
};
                       
           

我的修改後

//2018/12/24
class Solution {
public:
    bool canTransform(string start, string end) 
    {
        if(start.size() != end.size())
            return false;
        for(int i = 0; i < start.size(); i++)
        {
            if(start[i] == end[i])
               continue;
            if(end[i] == 'X')
            {
                if(start[i] == 'L')
                    return false;
                else
                {
                    int j = i + 1;
                    while(j < start.size())
                    {
                        if(start[j] == 'R')
                            j++;
                        else break;
                    }
                    if((j < start.size() ) && (start[j] == 'X'))
                       {
                           swap(start[i],start[j]);
                           continue;
                       }
                    else return false;       
                }
            }
            if(end[i] == 'R')
               return false;
            if(end[i] == 'L')
            {
                if(start[i] == 'R')
                    return false;
                else
                {
                    int j = i + 1;
                    while(j < start.size())
                    {
                        if(start[j] == 'X')
                            j++;
                        else break;
                    }
                    if( (j < start.size()) && (start[j] == 'L') )
                    {
                        swap(start[i],start[j]);
                        continue;
                    }
                    else return false;    
                }
            } 
            
        }
         return true;   
    }
};
           

别人的做法

class Solution {
public:
    bool canTransform(string start, string end) {
        if(start.length() != end.length())//長度不同，就算剔掉X之後相同，也是錯的
            return false;
        int i=0,j=0;
        while(i<end.length() && j<end.length()){
            while(start[i]=='X'){ //找到start串接下去的第一個非X字元
                i++;
            }
            while(end[j]=='X'){ //找到end串接下去的第一個非X字元
                j++;
            }
            //如果這倆個非X字元不同，則剔除掉X之後的串必然不同，是以是錯的。
            if(start[i] != end[j])
                return false;
            if(start[i] == 'L' && i<j)//同為L，但在start的位置先于其在end串的位置，也是錯的，L不能後移
                return false;
            if(start[i] == 'R' && i>j)
                return false;
            i++;
            j++;
        }
        return true;
    }
};