c++ - 将 s1 转换为以 s2 作为其子串的回文
问题描述
有人可以帮我理解这段代码吗
#include<bits/stdc++.h>
使用命名空间标准;
诠释主要(){
string s1,s2;
cin>>s1>>s2;
int l1=s1.length(),l2=s2.length();
int ans=INT_MAX;
if(l2>l1){
cout<<-1<<endl; // not possible
return 0;
}
for(int i=0 ; i<l1-l2+1 ; i++){
string temp=s1.substr(0,i)+s2+s1.substr(i+l2); // place s2 in all possible positions in s1
int cost=0;
// calculate cost to place s2
for(int j=i ; j<i+l2 ; j++){
if(s1[j]!=temp[j])
cost++;
}
int z=0;
// find the cost to convert new string to palindrome
有人可以解释下面的代码吗
for(int j=0 ; j<ceil(l1/2.0) ; j++){
if((j<i || j>=i+l2) && temp[j]!=temp[l1-j-1]) //(explain please) if s2 is in the first half of new string
cost++;
else if(temp[j]!=temp[l1-j-1] && (l1-j-1<i || l1-j-1>=i+l2)) // (explain please)if s2 is in the second half of new string
cost++;
else if(temp[j]!=temp[l1-j-1]){ // if s2 is in both halves
z=1;
break;
}
}
if(z==0)
ans=min(ans,cost);
}
if(ans==INT_MAX)
cout<<-1<<endl;
else
cout<<ans<<endl;
return 0;
}
解决方案
回文...向后与向前相同...代码的第一部分将 s2 覆盖在 s1 中从某个位置开始的字符之上:i。字符串 temp 是 s1 的前 i 个字符,然后是 s2 的所有字符,然后是 s1 中未覆盖的任何字符。temp 的长度应该是 s1 的长度。
在 j 循环中,您将迭代 0 到 s1 大小的一半向上舍入。
您的第一个“请解释”是查看字符串 temp 中的索引 j 是否落在属于 s1 的字符上(无论是在 s2 字符之前还是在它们之后)。它还查看 temp 中索引 j 处的字符是否匹配其在另一侧的位置(即该字符及其镜像是否已经相等,因为它们必须在回文中)。如果是 s1 的一部分,但不是匹配项,则您需要付出代价。
您的第二个“请解释”查看临时字符串的后半部分...它查看字符串 temp 中 j 镜像位置的字符是否落在 s1 的一部分的字符上,然后再次查看是否该位置的角色与其翻转相匹配……如果不是,则需要付出代价。
您基本上是在查看临时字符串中的字符,这些字符从字符串的末尾开始,一直到中间。所以你先看第一个字符。如果字符来自s1,则可以切换为最后一个字符。所以你只是增加成本。然后你看看 temp 中的最后一个字符。如果是来自 s1,则可以切换为第一个字符。所以你只是增加成本。现在递增 j,所以你正在查看第二个字符和第二个到最后一个字符,再次递增 j 你正在查看第三个字符和第三个到最后一个字符。等等等等……
如果在任何时候你不能交换前面的字符并且你不能交换后面的字符..那么如果它们不匹配,就不可能有回文。
推荐阅读
- android - 如何完成一项活动,但我不想去上一个活动(去另一个活动)
- ramda.js - 使用 ramda 在嵌套数组中查找具有给定 id 的对象,获取除子数组之外的所有属性
- maven - 找不到“groovy”的脚本引擎:scriptEngine 为空
- c++ - 我不明白这种重载是如何解决“工作”的
- android - 用于反应原生 0.60.5 的 Docker
- python-3.x - Jenkins Pipeiline - shell 命令为参数添加单引号
- microsoft-teams - 在 Microsoft Teams 中从移动设备上的消息启动操作?
- reactjs - 找不到 Apollo Client 实例
- c++ - Qt:长期适应未修改/独立于显示分辨率运行应用程序
- php - 在 Sylius 中过滤由发货网格处理的数据