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

我們已經給定了兩個字串，需要檢查給定字串的排列是否存在，以便一個排列可以比第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中文網其他相關文章！