检查给定字符串的任何排列是否按字典顺序大于另一个给定字符串

我们已经给定了两个字符串，需要检查给定字符串的排列是否存在，以便一个排列可以比第 i 个索引处的另一个排列具有更大的字符。

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

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

示例

输入 - str1 = "aef"; str2 = "fgh";

输出– 是

解释– ‘fgh’ 已经大于 ‘aef’。在这里，a > f, g > e, h > f。

输入– str1 = "adsm"; str2 = "obpc";

输出– 否

Explanation– 我们无法找到任何一种排列，使得其中一个字符串的每个字符都大于另一个排列。

方法 1

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

算法

• 使用 sort() 方法对字符串进行排序。

• 定义 isStr1Greater 布尔变量并使用 true 进行初始化。

• 遍历字符串，并且如果str1中第i个索引位置的字符小于str2，将isStr1Greater的值更新为false，并使用break关键字中断循环

• 如果 isStr1Greater 为真，则循环成功完成并返回真。

• 现在，遍历字符串以检查 str2 是否大于 str1。如果我们发现 str1 的任何字符都大于 str2，则返回 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中字符的频率存储到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};
   // 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)，因为我们在数组中存储字符的频率。

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

以上是检查给定字符串的任何排列是否按字典顺序大于另一个给定字符串的详细内容。更多信息请关注PHP中文网其他相关文章！