数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Java程序：检查一个字符串是否可以通过最多X次顺时针循环移位从另一个字符串生成
在这个问题中，我们需要通过对第一个字符串的每个字符执行最多x次循环移位操作来将其转换为另一个字符串。
解决该问题的朴素方法是对alpha1字符串的每个字符旋转x次，然后检查它是否与alpha2字符串在相同索引处的字符匹配。
第二种方法是通过查找相同索引处字符之间的循环差来解决问题。
问题陈述 – 我们给定一个正整数X。此外，我们还给定两个字符串alpha1和alpha2。任务是需要检查我们是否可以通过对alpha1的每个字符执行最多X次循环移位来将字符串alpha1转换为alpha2。如果可以将alpha1转换为alpha2，则打印“Yes”。否则，打印“No”。
示例
输入
alpha1 = "abc"; alpha2 = "def", x = 3
输出
‘Yes’
解释 – 我们可以将alpha1的每个字符最多旋转3次。因此，'a' + 3 == 'd'，'b' + 3 == 'e'，以及'c' + 3 == 'f'。
输入
alpha1 = "abc"; alpha2 = "dnf", x = 3
输出
‘No’
解释 – 不可能通过执行最多3次循环移位从'b'获得'n'。
输入
alpha1 = "stu"; alpha2 = "sxy", x = 9
输出
‘Yes’
解释 – 我们可以执行最多9次循环移位来更新任何字符。因此，对于's'到's'，我们需要0次循环移位，对于't'到'x'和'u'到'y'，我们需要4次循环移位，这小于9。因此，可以将alpha1转换为alpha2。
方法1
在这种方法中，我们将旋转alpha1的每个字符1到x次。如果我们找到与alpha2字符串字符的匹配项，我们将移动到下一个迭代。否则，我们可以说无法将alpha1转换为alpha2。
算法
步骤1 – 开始遍历alpha1字符串。
步骤2 – 如果alpha1和alpha2字符串中第p个索引处的字符相同，则移动到下一个迭代。否则，执行以下步骤。
步骤3 – 定义一个布尔变量'isCharSame'并将其初始化为false，以跟踪alpha2的字符是否与alpha1的字符在将其旋转q次后匹配。
步骤4 – 使用另一个嵌套循环进行x次迭代。在嵌套循环中，在取其对26取模后，将alpha1[p]和alpha2[p]的ASCII值存储到char1和char2中。
步骤5 – 将'q'添加到'char1'并取其对26取模，以将'char1'循环旋转'q'次。
步骤6 – 如果旋转后的字符值与'char2'匹配，则将'isCharSame'变量更改为true，并中断循环。
步骤7 – 在嵌套循环之外，如果'isCharSame'变量的值为false，则无法将alpha1转换为alpha2。
步骤8 – 最后，如果alpha1的所有字符在执行最多x次循环移位后都与alpha2匹配，则打印“Yes”。
示例
import java.io.*;
import java.util.*;
public class Main {
public static void CheckForConversion(String alpha1, String alpha2, int x) {
// variables to store character difference and string length
int str_len;
str_len = alpha1.length();
// Traverse both strings
for (int p = 0; p < str_len; p++) {
// If a character is not the same at the pth index in both strings
if (alpha1.charAt(p) != alpha2.charAt(p)) {
// variable to track if the character is the same after rotation
boolean isCharSame = false;
// Make X iterations
for (int q = 1; q <= x; q++) {
// Get a character from the pth index and find its ASCII value
int char1 = alpha1.charAt(p) % 26;
int char2 = alpha2.charAt(p) % 26;
// get character value between 1 to 26 after rotating by q index
int char1Result = (char1 + q) % 26;
// If chars are the same after adding q, break the loop
if (char1Result == char2) {
isCharSame = true;
break;
}
}
if (isCharSame == false) {
System.out.println("It is not possible to convert string alpha1 to alpha2 according to given conditions.");
return;
}
}
}
System.out.println("It is possible to convert string alpha1 to alpha2 according to given conditions.");
}
public static void main(String[] args) {
String alpha1 = "abc";
String alpha2 = "def";
int x = 3;
CheckForConversion(alpha1, alpha2, x);
}
}
输出
It is possible to convert string alpha1 to alpha2 according to given conditions.
时间复杂度 – O(N*X)，因为我们遍历字符串并将字符串的每个字符最多旋转X次。
空间复杂度 – O(1)，因为我们不使用动态空间。
方法2
在这种方法中，我们将取两个字符串的字符差。如果字符差大于X，则无法将alpha1字符串转换为alpha2。
算法
步骤1 – 初始化'char_diff'和'str_len'变量。
步骤2 – 开始迭代字符串。如果两个字符串中第p个索引处的字符相同，则使用'continue'关键字移动到字符串的下一个字符。
步骤3 – 从两个字符串的第p个索引访问字符，并从alpha2[p]中减去alpha1[p]的ASCII值。此外，将26添加到减法结果中并将其存储在'char_diff'变量中。
步骤4 – 取'char_diff'对26取模。
步骤5 – 如果任何字符的'char_diff'大于X，则打印'No'。此外，执行'return'语句以终止函数。
步骤6 – 最后，打印“Yes”。
示例
import java.io.*;
import java.util.*;
public class Main {
public static void CheckForConversion(String alpha1, String alpha2, int x) {
// variables to store character difference and string length
int char_diff = 0, str_len;
str_len = alpha1.length();
// Traverse both strings
for (int p = 0; p < str_len; p++) {
// If the character is the same at the pth index in both strings, move to the next iteration
if (alpha1.charAt(p) == alpha2.charAt(p))
continue;
// Difference calculation
char_diff = ((int) (alpha2.charAt(p) - alpha1.charAt(p)) + 26);
// Performing modulus operation for rotational difference
char_diff = char_diff % 26;
// If value of char_diff is more than x, it is not possible to convert string
// alpha1 to alpha2
if (char_diff > x) {
System.out.println("It is not possible to convert string alpha1 to alpha2 according to given conditions.");
return;
}
}
System.out.println("It is possible to convert string alpha1 to alpha2 according to given conditions.");
}
public static void main(String[] args) {
String alpha1 = "abc";
String alpha2 = "def";
int x = 3;
CheckForConversion(alpha1, alpha2, x);
}
}
输出
It is possible to convert string alpha1 to alpha2 according to given conditions.
时间复杂度 – O(N)，用于遍历字符串以检查每个字符的字符差。
空间复杂度 – O(1)
第一个解决方案找到字符的X次循环旋转并将其与另一个字符串的字符匹配，但第二个解决方案更符合逻辑，因为它使用字符差值来查找答案。
64次浏览
