Menyemak sama ada sebarang pilihatur rentetan tertentu secara leksikografi lebih besar daripada rentetan lain yang diberikan

Kami telah diberikan dua rentetan dan perlu menyemak sama ada pilih atur rentetan yang diberikan wujud supaya satu pilihatur boleh mempunyai aksara yang lebih besar daripada pilih atur lain pada indeks ke-i.

Kita boleh menyelesaikan masalah dengan mengisih rentetan dan membandingkan setiap aksara dalam rentetan itu satu demi satu. Sebagai alternatif, kita boleh menggunakan frekuensi aksara bagi dua rentetan untuk menyelesaikan masalah.

Pernyataan Masalah - Kami diberi rentetan str1 dan str2 panjang N. Kita perlu menyemak sama ada terdapat sebarang pilihatur rentetan supaya satu lebih besar dari segi leksikografi daripada yang lain. Ini bermakna bahawa sebarang pilih atur harus mempunyai aksara pada indeks ke-i yang lebih besar daripada aksara pada indeks ke-i bagi pilihatur rentetan yang lain.

Contoh

Input - str1 = "aef"; str2 = "fgh";

Output–Ya

Penjelasan– ‘fgh’ sudah lebih besar daripada ‘aef’. Di sini, a >

Input– str1 = "adsm"; str2 = "obpc";

Output–Tidak

Penjelasan– Kami tidak dapat menjumpai sebarang pilihatur di mana setiap aksara bagi satu rentetan lebih besar daripada yang lain.

Kaedah 1

Dalam kaedah ini, kita akan menyusun dua rentetan dalam susunan leksikografi. Kami kemudian akan membandingkan setiap aksara rentetan. Mengembalikan benar jika semua aksara str1 kurang daripada str2, atau jika semua aksara str2 kurang daripada str1. Jika tidak, pulangkan palsu.

Algoritma

• Gunakan kaedah sort() untuk mengisih rentetan.

• Tentukan pembolehubah boolean isStr1Greater dan mulakannya dengan benar.

• Lintas rentetan dan jika aksara pada kedudukan indeks ke-i dalam str1 kurang daripada str2, kemas kini nilai isStr1Greater kepada palsu dan gunakan kata kunci putus untuk mengganggu gelung

• Jika isStr1Greater adalah benar, gelung berjaya diselesaikan dan mengembalikan benar.

• Sekarang, gelung melalui rentetan untuk menyemak sama ada str2 lebih besar daripada str1. Jika kita mendapati bahawa mana-mana aksara str1 lebih besar daripada str2, maka false dikembalikan.

• Kembalikan benar jika gelung berjaya diselesaikan.

Contoh

#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;
}

Output

Yes, permutation exists such that one string is greater than the other.

Kerumitan masa - O(N*logN) kerana kami mengisih rentetan.

Kerumitan Ruang - O(N) diperlukan untuk mengisih rentetan.

Kaedah 2

Dalam kaedah ini kita akan menyimpan jumlah kekerapan setiap aksara dalam kedua-dua rentetan. Selepas itu, kami akan menggunakan kekerapan terkumpul untuk memutuskan sama ada kami boleh mencari sebarang pilih atur rentetan supaya satu lebih besar daripada yang lain.

Algoritma

• Tentukan tatasusunan peta1 dan peta2 dengan panjang 26 dan mulakannya kepada sifar.

• Simpan kekerapan aksara dalam str1 ke dalam peta1 dan simpan kekerapan aksara dalam str2 ke dalam peta2.

• Tentukan pembolehubah boolean isStr1 dan isStr2 dan mulakannya kepada false untuk menjejaki sama ada str1 lebih besar daripada str2.

• Tentukan pembolehubah cnt1 dan cnt2 untuk menyimpan kekerapan kumulatif aksara rentetan.

• Merentasi peta1 dan peta2. Tambahkan map1[i] pada cnt1 dan map2[i] kepada cnt2.

• Jika cnt1 lebih besar daripada cnt2, kekerapan kumulatif aksara dari str1 ke indeks ke-i adalah lebih besar. Jika ya, dan str2 sudah lebih besar, kembalikan palsu. Jika tidak, tukar isStr1 kepada true

• Jika cnt2 lebih besar daripada cnt1, maka kekerapan kumulatif aksara pada indeks ke-i dalam str2 adalah lebih besar. Jika ya, dan str1 sudah lebih besar, kembalikan palsu. Jika tidak, tukar isStr2 kepada true

• Akhirnya kembali benar.

Contoh

#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;
}

Output

Yes, permutation exists such that one string is greater than the other.

Kerumitan masa - O(N), kerana kita mengira kekerapan aksara.

Kerumitan ruang - O(26) kerana kami menyimpan kekerapan aksara dalam tatasusunan.

Kami belajar untuk menyemak sama ada terdapat sebarang pilihatur dua rentetan supaya semua aksara satu rentetan boleh lebih besar daripada rentetan yang lain. Kaedah pertama menggunakan kaedah pemeringkatan, dan kaedah kedua menggunakan kekerapan kumulatif aksara.

Atas ialah kandungan terperinci Menyemak sama ada sebarang pilihatur rentetan tertentu secara leksikografi lebih besar daripada rentetan lain yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!