資料結構
網路
關係資料庫管理系統
作業系統
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次瀏覽
