首頁 > 後端開發 > C++ > 檢查一個字串是否可以透過交換二進位字串中具有不相等字元的索引處的字元對來形成回文字串

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

PHPz
發布: 2023-09-02 20:09:11
轉載
1188 人瀏覽過

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

問題陳述

我們有一個字串str和一個二進位字串B。兩個字串的長度都等於N。我們需要檢查是否可以透過在字串B中包含不相等字符的任意索引對上多次交換其字符,使字串str成為回文字串。

範例範例

輸入

1

str = ‘AAS’ B = ‘101’

登入後複製

輸出

1

‘YES’

登入後複製

Explanation

的中文翻譯為:

解釋

我們可以交換str[1]和str[2],因為B[1]和B[2]不相等。最終的字串可以是'ASA'。

輸入

1

str = ‘AASS’ B = ‘1111’

登入後複製

輸出

1

‘No’

登入後複製
登入後複製

Explanation

的中文翻譯為:

解釋

我們無法讓字串回文,因為字串B不包含不相等的字元。

輸入

1

str = ‘AASSBV’ B = ‘111100’

登入後複製

輸出

1

‘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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

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

}

登入後複製

輸出

1

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

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

}

登入後複製

輸出

1

Yes

登入後複製
登入後複製
  • 時間複雜度 - O(N),因為我們使用for迴圈來遍歷字串。

  • 空間複雜度 − O(1),因為我們總是使用長度為26的陣列。

結論

我們學習了兩種方法來檢查字串是否可以根據給定條件交換字元而成為回文。第一種方法使用集合和映射,而第二種方法僅使用陣列來儲存資料。第二種方法比第一種方法更好,因為insert()方法在集合中插入資料需要O(logn)的時間,而陣列只需要O(1)的時間。

以上是檢查一個字串是否可以透過交換二進位字串中具有不相等字元的索引處的字元對來形成回文字串的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:tutorialspoint.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板