检查一个字符串是否可以通过交换二进制字符串中具有不相等字符的索引处的字符对来形成回文字符串

问题陈述

我们有一个字符串str和一个二进制字符串B。两个字符串的长度都等于N。我们需要检查是否可以通过在字符串B中包含不相等字符的任意索引对上多次交换其字符，使字符串str成为回文字符串。

示例示例

输入

str = ‘AAS’ B = ‘101’

输出

‘YES’

Explanation

的中文翻译为：

解释

我们可以交换str[1]和str[2]，因为B[1]和B[2]不相等。最终的字符串可以是'ASA'。

输入

str = ‘AASS’ B = ‘1111’

输出

‘No’

Explanation

的中文翻译为：

解释

我们无法使字符串回文，因为字符串B不包含不相等的字符。

输入

str = ‘AASSBV’ B = ‘111100’

输出

‘No’

Explanation

的中文翻译为：

解释

由于字符频率不匹配，我们无法使字符串str成为回文。

方法一

在第一种方法中，我们将检查是否可以使用字符串str的所有字符创建任何回文字符串。如果是，我们可以检查是否可以交换字符串B中包含不相等字符的索引对中的字符，并使字符串成为回文。否则，我们返回false。

算法

• 步骤 1 - 执行 utility() 函数，根据给定条件交换字符来判断字符串是否可以通过交换字符成为回文。

• 第二步 - 定义canBePalindromic()函数来检查我们是否可以使用str的字符来构造任何回文字符串。

• 步骤 2.1 − 创建一个映射，用于存储字符串 str 中每个字符及其频率。使用 for 循环遍历字符串并计算字符的频率。

• 第2.2步 - 计算具有偶数和奇数频率的字符数量。

• 步骤 2.3 - 使用 set 来获取字符串中唯一字符的总数。

• 步骤 2.4 − 如果字符串长度为奇数并且只包含一个具有奇数频率的字符，则返回 true。

• 步骤 2.5 − 如果字符串长度为偶数，则所有具有偶数频率的字符，以及0个具有奇数频率的字符，返回true。

• 步骤 2.6 − 返回 false。

• 第三步 - 如果字符串不能成为回文，返回false。

• 第四步 - 如果字符串B中包含多个'1'和'0'，则返回true；否则，返回false。

Example

#include <bits/stdc++.h>
using namespace std;
// function to check if the string can be palindromic
bool canBePalindromic(string str){
   //Creating the map to store the frequency of each character
   map<char, int> charMap;
   // store the frequency of each character of string Str
   for (int i = 0; i < str.length(); i++) {
      charMap[str[i]] += 1;
   }
   // to store the count of even and odd frequent characters
   int even = 0, odd = 0;
   // iterate through the map
   for (auto e : charMap)  {
      //If frequency is odd, increment odd count; else, increment even count
      if (e.second % 2 == 1) {
         odd++;
      } else {
         even++;
      }
   }
   // set to store unique characters of string Str
   unordered_set<char> set;
   //Insert all characters of string Str in set
   for (int i = 0; i < str.size(); i++){
      set.insert(str[i]);
   }
   // if the string length is odd and only one character has an odd frequency, return true
   if (str.size() % 2 == 1 && even == set.size() - 1 && odd == 1){
      return true;
   }
   // If the string length is even and all characters have even frequency, return true
   if (str.size() % 2 == 0 && even == set.size() && odd == 0){
      return true;
   }
   // else return false
   return false;
}
// function to check if the string can be palindromic by swapping characters according to string B
bool utility(string S, string B){
   // If string S cannot be palindromic, return false.
   if (canBePalindromic(S) == false){
      return false;
   } else{
      // if at least one '1' and '0' is present in string B, string S can be palindromic
      int one = 0, zero = 0;
      for (int i = 0; i < B.size(); i++) {
         // If the current character is '0.'
         if (B[i] == '0'){
            zero++;
         } else {
            one++;
         }
      }
      // return true if at least one '1' and '0' is present in the string B
      if (one >= 1 && zero >= 1){
         return true;
      } else {
         return false;
      }
   }
}
int main(){
   string S = "NANA";
   string B = "0001";
   bool result = utility(S, B);
   if (result)
      cout << "Yes";
   else
      cout << "No";
   return 0;
}

输出

Yes

• 时间复杂度 - O(NlogN)，因为我们使用for循环遍历字符串，并且set的insert()方法需要(logN)的时间。

• 空间复杂度 - O(K)，其中K是唯一字符的总数。

方法二

在这种方法中，我们将使用一个数组来存储字符的频率，而不是使用一个映射。

算法

• 步骤 1 - 创建一个长度为26的'charFrequancy'数组，并初始化为零。

• 第二步 - 计算字符串B中的1和0的总数。

• 第三步 - 更新数组中每个字符的频率。

• 第四步 - 如果字符串长度为偶数且奇数频率不为零，则返回false。

• 步骤5 - 如果字符串长度为奇数且奇数频率大于1，则返回false。

• 步骤 6 - 如果字符串中同时存在 1 和 0，则返回 true。

• 第7步 - 返回 false。

Example

#include <bits/stdc++.h>
using namespace std;
// function to check if the given string can be converted to a palindrome
bool utility(string str, string B){
   // array to store character counts in str
   int charFrequancy[26] = {0};
   int ones = 0, zeros = 0, odd_fre = 0;
   // count ones and zeros
   for (char ch : B) {
      if (ch == '1')
         ones++;
      if (ch == '0')
         zeros++;
   }
   // store counts of characters
   for (char ch : str){
      charFrequancy[ch - 'A']++;
   }
   // check total character with odd frequency
   for (int i = 0; i < 26; i++){
      if (charFrequancy[i] % 2 == 1)
         odd_fre++;
   }
   if (str.length() % 2 == 0 && odd_fre != 0)
      return false;
   if (str.length() % 2 == 1 && odd_fre > 1)
      return false;
   if (ones > 0 && zeros > 0)
      return true;
   return false;
}
int main(){
   string S = "NBCNB";
   string B = "01010";
   if (utility(S, B)){
      cout << "Yes";
   } else {
      cout << "No";
   }
   return 0;
}

输出

Yes

• 时间复杂度 - O(N)，因为我们使用for循环来遍历字符串。

• 空间复杂度 − O(1)，因为我们始终使用长度为26的数组。

结论

我们学习了两种方法来检查字符串是否可以通过根据给定条件交换字符而成为回文。第一种方法使用集合和映射，而第二种方法仅使用数组来存储数据。第二种方法比第一种方法更好，因为insert()方法在集合中插入数据需要O(logn)的时间，而数组只需要O(1)的时间。

以上是检查一个字符串是否可以通过交换二进制字符串中具有不相等字符的索引处的字符对来形成回文字符串的详细内容。更多信息请关注PHP中文网其他相关文章！