C++ 检查给定字符串的任意排列是否字典序大于另一个给定字符串

我们给出了两个字符串，我们需要检查给定字符串的排列是否存在，使得某个排列在第i个索引处的字符比另一个排列的字符更大。

我们可以通过对字符串进行排序，并逐个比较字符串的每个字符来解决这个问题。同时，我们也可以利用两个字符串的字符频率来解决这个问题。

问题陈述 - 给定长度为N的字符串str1和str2，我们需要检查是否存在两个字符串的任意排列，其中一个字符串的排列在另一个字符串的排列之上。这意味着任意排列应该在第i个索引处具有比另一个字符串的排列的第i个索引字符更大的字符。

示例

输入 - str1 = “aef”; str2 = “fgh”;

输出 - Yes

解释 - “fgh”已经大于”aef”。这里，a > f, g > e, h > f。

输入 - str1 = “adsm”; str2 = “obpc”;

输出 - No

解释 - 我们无法找到任何两个字符串的排列，使得其中一个字符串的每个字符都大于另一个排列的对应字符。

方法1

在这种方法中，我们将两个字符串按照字典顺序进行排序。然后，我们将逐个比较字符串中的每个字符。如果str1的所有字符都小于str2，或者str2的所有字符都小于str1，则返回true。否则返回false。

步骤

• 使用sort()方法对字符串进行排序。
• 定义一个布尔变量isStr1Greater，并将其初始化为true。
• 遍历字符串，如果在str1的第i个索引处的字符小于str2，则将isStr1Greater的值更新为false，并使用break关键字中断循环。
• 如果isStr1Greater为true，则循环成功完成，并返回true。
• 现在，遍历字符串以检查str2是否大于str1。如果发现str1的任何字符更大，则返回false。
• 如果循环成功完成，则返回true。

示例

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

bool isAnyPermLarge(string string1, string string2) {
   // sort the strings
   sort(string1.begin(), string1.end());
   sort(string2.begin(), string2.end());
   // to keep track if string1 is greater than string2
   bool isStr1Greater = true;
   // traverse the string
   for (int i = 0; i < string1.length(); i++) {
      // if any character of string1 is less than string2, return false.
      if (string1[i] < string2[i]) {
          isStr1Greater = false;
          break;
      }
   }
   // If string1 is greater, returning true
   if (isStr1Greater)
      return true;
   // traverse the string
   for (int i = 0; i < string2.length(); i++) {
      // if any character of string2 is less than string1, return false.
      if (string1[i] > string2[i]) {
          return false;
      }
   }
   // return true if string2 is greater than string1
   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和str2的字符频率存储到map1和map2中。

• 定义isStr1和isStr2的布尔变量，并初始化为false，以跟踪str1是否大于str2。

• 定义cnt1和cnt2变量，用于存储字符串字符的累积频率。

• 遍历map1和map2。将map1[i]添加到cnt1中，将map2[i]添加到cnt2中。

• 如果cnt1大于cnt2，表示累积频率直到第i个索引的字符对于str1来说更大。如果是这样，并且str2已经更大，则返回false。否则，将isStr1更改为true。

• 如果cnt2大于cnt1，表示累积频率直到第i个索引的字符对于str2来说更大。如果是这样，并且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};
   // store the frequency of each character in the map1
   for (int i = 0; i < string1.length(); i++) {
      map1[string1[i] - 'a']++;
   }
   // store the frequency of each character in the map2
   for (int i = 0; i < string2.length(); i++) {
      map2[string2[i] - 'a']++;
   }
   // To keep track of which string is smaller. Initially, both strings are equal.
   bool isStr1 = false, isStr2 = false;
   // to count the cumulative frequency of characters of both strings
   int cnt1 = 0, cnt2 = 0;
   // traverse for all characters.
   for (int i = 0; i < 26; i++) {
      // update the cumulative frequency of characters
      cnt1 += map1[i];
      cnt2 += map2[i];
      if (cnt1 > cnt2) {
          // If string2 is already greater and cumulative frequency of string1 is greater than string2, then return false
          if (isStr2)
              return false;
          // update isStr1 to true as string1 is smaller
          isStr1 = true;
      }
      if (cnt1 < cnt2) {
          // If string1 is already greater and cumulative frequency of string2 is greater than string1, then return false
          if (isStr1)
              return false;
          // update isStr2 to true as string2 is smaller
          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），因为我们将字符的频率存储在一个数组中。

我们学会了检查是否存在任何一个字符串的排列，使得其中一个字符串的所有字符都可以大于另一个字符串的字符。第一种方法使用排序方法，第二种方法使用字符的累积频率。