检查给定字符串的任何排列是否按字典顺序大于另一个给定字符串
我们给出了两个字符串，需要检查给定字符串的排列是否存在，使得一个排列可以具有比第 i 个索引处的另一个排列更大的字符。
我们可以通过对字符串进行排序并逐一比较字符串的每个字符来解决问题。此外，我们可以使用两个字符串的字符频率来解决问题。
问题陈述– 我们给出了长度为 N 的字符串 str1 和 str2。我们需要检查两个字符串是否存在任何排列，使得一个字符串的排列按字典顺序大于另一个字符串。这意味着任何排列在第 i 个索引处的字符都应该比其他字符串排列的第 i 个索引字符更大。
示例
输入– str1 = "aef"; str2 = "fgh";
输出– 是
解释– 'fgh' 已经大于 'aef'。这里，a > f，g > e，h > f。
输入– str1 = "adsm"; str2 = "obpc";
输出– 否
解释– 我们找不到两个字符串的任何排列，使得其中一个的每个字符都大于另一个排列。
方法 1
在这种方法中，我们将按字典顺序对两个字符串进行排序。之后，我们将比较字符串的每个字符。如果 str1 的所有字符都小于 str2，或者 str2 的所有字符都小于 str1，则返回 true。否则返回 false。
算法
使用 sort() 方法对字符串进行排序。
定义 isStr1Greater 布尔变量并用 true 初始化。
遍历字符串，如果 str1 中第 i 个索引处的任何字符小于 str2，则将 isStr1Greater 的值更新为 false，并使用 break 关键字中断循环
如果 isStr1Greater 为 true，则循环成功完成并返回 true。
现在，遍历字符串以检查 str2 是否大于 str1。如果我们发现 str1 的任何字符大于 str2，则返回 false。
如果循环成功完成，则返回 true。
示例
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
bool isAnyPermLarge(string string1, string string2) {
// 对字符串进行排序
sort(string1.begin(), string1.end());
sort(string2.begin(), string2.end());
// 跟踪 string1 是否大于 string2
bool isStr1Greater = true;
// 遍历字符串
for (int i = 0; i < string1.length(); i++) {
// 如果 string1 中的任何字符小于 string2，则返回 false。
if (string1[i] < string2[i]) {
isStr1Greater = false;
break;
}
}
// 如果 string1 大于，则返回 true
if (isStr1Greater)
return true;
// 遍历字符串
for (int i = 0; i < string2.length(); i++) {
// 如果 string2 中的任何字符小于 string1，则返回 false。
if (string1[i] > string2[i]) {
return false;
}
}
// 如果 string2 大于 string1，则返回 true
return true;
}
int main() {
string string1 = "aef";
string string2 = "fgh";
bool res = isAnyPermLarge(string1, string2);
if (res) {
cout << "Yes, permutation exists such that one string is greater than the other.";
} else {
cout << "No, permutation does not exist such that one string is greater than the other.";
}
return 0;
}
输出
Yes, permutation exists such that one string is greater than the other.
时间复杂度 – 对字符串进行排序时为 O(N*logN)。
空间复杂度 – 对字符串进行排序需要 O(N)。
方法 2
在此方法中，我们将存储两个字符串中每个字符的总频率。之后，我们将使用累积频率来决定是否能找到任何字符串排列，使得一个大于另一个。
算法
定义长度为 26 的 map1 和 map2 数组，并将其初始化为零。
将 str1 的字符频率存储到 map1，将 str2 的字符频率存储到 map2。
定义 isStr1 和 isStr2 布尔变量，并将其初始化为 false，以跟踪 str1 是否大于 str2。
定义 cnt1 和 cnt2 变量以存储字符串字符的累积频率。
遍历 map1 和 map2。将 map1[i] 添加到 cnt1，将 map2[i] 添加到 cnt2。
如果 cnt1 大于 cnt2，则 str1 中第 i 个索引处的字符的累积频率较大。如果是这样，并且 str2 已经较大，则返回 false。否则，将 isStr1 更改为 true
如果 cnt2 大于 cnt1，则 str2 中第 i 个索引处的字符的累积频率较大。如果是这样，并且 str1 已经较大，则返回 false。否则，将 isStr2 更改为 true
最后返回 true。
示例
#include <iostream>
#include <string>
using namespace std;
bool isAnyPermLarge(string string1, string string2) {
int map1[26] = {0};
int map2[26] = {0};
// 将每个字符的频率存储在 map1 中
for (int i = 0; i < string1.length(); i++) {
map1[string1[i] - 'a']++;
}
// 将每个字符的频率存储在 map2 中
for (int i = 0; i < string2.length(); i++) {
map2[string2[i] - 'a']++;
}
// 跟踪哪个字符串较小。最初，两个字符串相等。
bool isStr1 = false, isStr2 = false;
// 计算两个字符串的字符累积频率
int cnt1 = 0, cnt2 = 0;
// 遍历所有字符。
for (int i = 0; i < 26; i++) {
// 更新字符的累积频率
cnt1 += map1[i];
cnt2 += map2[i];
if (cnt1 > cnt2) {
// 如果 string2 已经大于 string1 并且累积频率大于 string2，则返回 false
if (isStr2)
return false;
// 由于 string1 较小，因此将 isStr1 更新为 true
isStr1 = true;
}
if (cnt1 < cnt2) {
// 如果 string1 已经大于，并且 string2 的累积频率大于 string1，则返回 false
if (isStr1)
return false;
// 由于 string2 较小，因此将 isStr2 更新为 true
isStr2 = true;
}
}
return true;
}
int main() {
string string1 = "aef";
string string2 = "fgh";
bool res = isAnyPermLarge(string1, string2);
if (res) {
cout << "Yes, permutation exists such that one string is greater than the other.";
} else {
cout << "No, permutation does not exist such that one string is greater than the other.";
}
return 0;
}
输出
Yes, permutation exists such that one string is greater than the other.
时间复杂度 – O(N)，因为我们计算字符的频率。
空间复杂度 – O(26)，因为我们将字符的频率存储在数组中。
我们学会了检查两个字符串是否存在任何排列，使得一个字符串的所有字符都可以大于另一个字符串。第一种方法使用排序方法，第二种方法使用字符的累积频率。
