题目
在一个由 ‘L’ , ‘R’ 和 ‘X’ 三个字符组成的字符串（例如\"RXXLRXRXL\"）中进行移动操作。一次移动操作指用一个\"LX\"替换一个\"XL\"，或者用一个\"XR\...
题目
在一个由 ‘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;
}
};
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：修改UI及盒子启动及部分后续操作 下一篇：Linux系统命令归纳
