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的字符在经过旋转q次后是否与alpha1的字符匹配。

步骤 4 – 使用另一个嵌套循环进行x次迭代。在嵌套循环中，将alpha1[p]和alpha2[p]的ASCII值存储到char1和char2中，然后对其进行26的模运算。

步骤 5 – 将’q’添加到’char1’并对26取模，以将’char1’进行循环移位’q’次。

步骤 6 – 如果旋转后的字符值与’char2’匹配，则将’isCharSame’变量更改为true，并跳出循环。

步骤 7 – 在嵌套循环之外，如果’isCharSame’变量的值为false，则无法将alpha1转换为alpha2。

步骤 8 – 最后，如果在最多进行x次循环移位后，alpha1的所有字符与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索引处的字符，并从alpha1[p]的ASCII值中减去alpha2[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个字符的循环旋转，并将其与另一个字符串的字符进行匹配，但第二种解决方案更合乎逻辑，因为它使用字符差异值来找到答案。