檢查給定字串的任何排列是否按字典序大於另一個給定字串

---

我們給出了兩個字串，需要檢查是否存在給定字串的排列，使得一個排列在第 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 的任何字元更大，則返回 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)，因為我們將字元的頻率儲存在陣列中。

我們學習瞭如何檢查是否存在這兩個字串的任何排列，使得一個字串的所有字元都大於另一個字串。第一種方法使用排序方法，第二種方法使用字元的累積頻率。