题目详情
给定两个字符串，仅由小写字母组成，它们包含了相同字符。
求把第一个字符串变成第二个字符串的最小操作次数，且每次操作只能对第一个字符串中的某个字符移动到此字符串中的开头。
例如给定两个字符串“abcd" "bcad" ，输出：2，因为需要操作2次才能把"abcd"变成“bcad" ，方法是：abcd->cabd->bcad。
要将第一个字符串a（abcd）转换为目标字符串b(bcad)，根据题目的要求，分析可知，最简单的方法就是按照目标字符串的逆序来操作，既先把d提前，然后a , c, b;这样肯定能转换为目标字符串。然后我来优化这个算法，首先比较两个字符串的最后面的一个字符，如果是一样的，那么它就不需要被提前。直接然两个字符串都去掉最后一个字符，接着比较。
如果发现两个字符串的尾字符不相同（abc）到(bca)，那么我们必须要操作字符了。我先找到目标字符串的最后一个字符(a)，那么待转换字符串(abc)中'a'（从后面数第一个）后面的bc是肯定需要操作的。但是怎么来操作呢？我来看看目标字符串倒数第二个字符是
'c'，那么很显然，我们应该先将bc中的'c'先提前。但是如果是cabc到cbca这时我们发现目标字符串的c在带转换字符串中'a'的前面也有一个，那么就要在目标字符串(cbca)中继续向前找，是'b‘。这时在待转换字符串的前面没有bca与它匹配.那么就操作这个b。然后继续这么比较下去。
在上面的想法下，写了下面的算法，但是结果却是执行测试用例失败!解析这组数据出错了：2。我不知道哪儿不对。希望大家指点指点，讨论一下。
int CalSwapStringNum(string sDis, string sIn)
{
int iSwapNum = 0;
size_t iLength = sDis.length();//记录要操作字符串的长度
if (sIn.length() != iLength)
{
return -1;
}
char cDe;//目标字符串最后一个字符
while(iLength > 0)
{
if (sDis[iLength - 1] != sIn[iLength - 1])//如果最后的字符不相同
{
cDe = sDis[iLength - 1];
int iPosE = sIn.find_last_of(cDe);//找到对应待转换字符串中对应字符位置
if (iPosE == string::npos)
{
return -1;
}
int iBefore = 0;//比较字符在最后一个字符前面多少
while(iPosE - iBefore - 1 >=0)//找到目标字符串中优先比较字符的位置
{
if (sIn[iPosE - iBefore - 1] == sDis[iLength - 2 - iBefore])
{
iBefore++;
continue;
}
break;
}
const int iLastNum = iLength - iPosE - 1;//必须要操作的次数
iSwapNum += iLastNum;
for (int i = 0; i < iLastNum; i++)
{
int iBef = 0;
int iPosE2;//先操作字符的位置
while(iBef <= iLength - 2 - i - iBefore)
{
char cDe2 = sDis[iLength - 2 - i - iBef - iBefore];
iPosE2 = sIn.find_last_of(cDe2);
if (iPosE2 > iPosE + i)
{
break;
}
iBef ++;
}
if (iBef > iLength - 2 - i - iBefore)
{
return -1;//没有找到
}
//把iposE2位置的字符提到最前
char cTemp = sIn[iPosE2];
sIn.erase(iPosE2, 1);//去掉这个位置的字符
sIn.insert(sIn.begin(), cTemp);//将它加到最前面
}
}
sDis.erase(iLength - 1, 1);//最后一个字符去除
sIn.erase(iLength - 1, 1);//最后一个字符去除
iLength--;//字符串长度
}
return iSwapNum;
}