当先锋百科网

首页 1 2 3 4 5 6 7

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