C++程序 检查一个字符串是否可以通过至多X次循环顺时针移位从另一个字符串形成
给定一个整数 X 和两个字符串 S1 和 S2 ,任务是检查字符串 S1 能否通过至多将字符循环顺时针移动X次转换为字符串 S2 。
输入: S1 =“abcd”,S2 =“dddd”,X = 3
输出: 是的
说明:
给定字符串S1可以转换为字符串S2,如下所示-
字符“a” – 移动3次 – “d”
字符“b” – 移动2次 – “d”
字符“c” – 移动1次 – “d”
字符“d” – 移动0次 – “d”
输入: S1 =“you”,S2 =“ara”,X = 6
输出: 是的
说明:
给定字符串S1可以转换为字符串S2,如下所示-
字符“y” – 循环移动2次 – “a”
字符“o” – 移动3次 – “r”
字符“u” – 循环移动6次 – “a”
计算方法: 遍历字符串,并对每个索引找到两个字符串中相应索引的字符的ASCII值之间的差。如果差小于0,则循环移位时添加26以获取实际差值。如果任何索引的差超过 X ,则 S2 不能从 S1 形成,否则可能可以。
下面是上述方法的实现:
// C ++实现以检查
//是否可以通过循环
//按顺时针方向移动的方式将给定字符串转换为另一个字符串
//超过X次
#include
using namespace std;
//检查是否可以通过循环将s1的所有字符转换为s2,可顺时针旋转X次
void isConversionPossible(string s1,
string s2, int x)
{
int diff, n;
n = s1.length();
//检查字符的所有线程
//字符串,它们的差值
// ASCII值小于
// X或不
for (int i = 0; i < n; i++) {
//如果两个字符相同
if (s1[i] == s2[i])
continue;
//计算差异
//字符的ASCII值
diff = (int(s2[i] - s1[i])
+ 26)
% 26;
//如果差异超过X
if (diff > x) {
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
//驱动程序代码
int main()
{
string s1 = "you";
string s2 = "ara";
int x = 6;
//调用功能
isConversionPossible(s1, s2, x);
return 0;
}
输出:
YES
时间复杂度: O(N),N=Length(S1) 辅助空间: O(1)