檢查一個字串是否可以透過交換二進位字串中具有不相等字元的索引處的字元對來形成回文字串

問題陳述

我們有一個字串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中文網其他相關文章！