数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学检查字符串 A 是否可以通过将 A[i] 更改为 A[i+1] 或将 A[i]..A[i+K-1] 更改为 A[i]+1 来转换为字符串 B
给定两个字符串，我们必须检查是否可以通过多次执行特定给定任务来将第一个字符串转换为另一个字符串。这些任务只能对给定的第一个字符串执行，并且任务是：
选择任何索引 i，使得 i < length(A) -1，并将第 i 个字符与下一个字符交换。
给定一个整数 k，我们只能选择第一个字符串中任何连续的 k 个索引，如果它们相同，则可以将它们更新为下一个字符（如果可能，字符 'z' 不可以）。例如：可以将 'a' 更新为 'b'，'c' 更新为 'd'，'y' 更新为 'z' 等。
我们必须说明是否可以通过任意次数应用上述给定任务来使两个给定字符串相等。
示例
输入
string str1 = “abcbcacba” string str2 = “xxxyyyzzz” int k = 3
输出
Yes, it is possible to convert the first string to the second
解释：第一个字符串中有三个字符 a、b 和 c。此外，所有三个字符的频率相同。我们可以将字符 'a' 的频率一起增加到 'z'，因为第二个字符串中有三个 'z'，同样地，b 到 x，c 到 y。
输入
string str1 = “abcbcacba” string str2 = “xxxzzzyyy” int k = 2;
输出
No, it is not possible to convert the first string to the second
解释：由于 k 的值为 2，我们只能对两个字符进行分组，而我们不同的字符成对出现 3 个，因此无法更改它们。
观察
我们必须使两个字符串相等，并且我们只能应用上述给定的操作。我们可以在这里进行的观察是：
我们可以任意多次交换字符，因此字符的顺序无关紧要，唯一重要的是字符的频率。
我们可以增加字符的频率，而不能减少它，因此，如果有一些字符的 ASCII 值大于第二个字符串中最大字符的 ASCII 值，那么就不可能使两个字符串相同。
此外，如果两个字符串的大小不同，那么显然不可能使两个字符串相同。
方法
我们已经看到了问题的示例和观察结果，让我们转到实现步骤。
首先，我们将检查字符串长度，如果字符串长度不同，则不可能使它们相等，因此返回 false。
我们将创建两个数组来存储两个字符串中字符的频率。
然后，我们将使用 for 循环遍历字符串以获取频率。
之后，我们将使用一个额外的变量遍历频率数组来计算剩余的额外字符。
我们将使用 if-else 条件来检查是否可以根据当前索引的频率使字符串与当前索引相同。
示例
#include <bits/stdc++.h>
using namespace std;
bool isPos(string str1, string str2, int k){
int len = str1.size(); // getting length of the string 1
// if the length of both the strings is not the same then return false
if(len != str2.size()){
return false;
}
// getting the frequency of the characters
int freq1[26] = {0};
int freq2[26] = {0};
// getting the frequencies
for(int i=0; i<len; i++){
freq1[str1[i]-'a']++;
}
for(int i=0; i<len; i++){
freq2[str2[i]-'a']++;
}
int cnt = 0; // maintaining count of the remaining characters
// traversing over the frequency array
for(int i=0; i<26; i++){
freq1[i] += cnt; // adding the previous characters which are more
if(freq2[i] > freq1[i]){
// we are not able to create the string
return false;
}
else if((freq1[i] - freq2[i]) % k){
// some characters lefts which are not multiple of k and we are not able to make them same of another
return false;
} else{
cnt += freq1[i]-freq2[i];
}
}
return true;
}
int main(){
// given string
string str1 = "abccbabca";
string str2 = "xxxzzzyyy";
int k = 3; // given number
// calling to the function
bool res = isPos(str1, str2, k);
if(res == true){
cout<<"Yes, it is possible to convert the first string to the second"<<endl;
} else{
cout<<"No, it is not possible to convert the first string to the second"<<endl;
}
}
输出
Yes, it is possible to convert the first string to the second
时间和空间复杂度
上述代码的时间复杂度为 O(N)，其中 N 是给定字符串的大小。
上述代码的空间复杂度为 O(1) 或常数，因为我们使用了额外的空间，但是该空间对于所有输入大小都是常数。
结论
在本教程中，我们实现了一个程序来检查如果我们在第一个字符串上执行无限数量的给定操作，则是否可以使两个给定字符串相等。这些操作是：选择任何索引 i，使得 i < length(A) -1，并将第 i 个字符与下一个字符交换；以及给定一个整数 k，我们只能选择第一个字符串中任何连续的 k 个索引，如果它们相同，则可以将它们更新为下一个字符。我们已经以线性时间和常数空间复杂度实现了该程序。
78 次查看
