我們已經給定了兩個字符串，需要檢查給定字符串的排列是否存在，以便一個排列可以比第 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)，因為我們在數組中存儲字符的頻率。
我們學會了檢查兩個字符串是否存在任何排列，使得一個字符串的所有字符都可以大于另一個字符串。第一種方法采用排序方法，第二種方法采用字符累積頻率。
以上就是檢查給定字符串的任何排列是否按字典順序大于另一個給定字符串的詳細內容，更多請關注www.xfxf.net其它相關文章！
