透過插入給定字元使字串非迴文

---

問題陳述

輸入中給定一個字串 str 和字元 c。我們需要在字串的索引處插入給定的字元 c，以便將字串轉換為非迴文。如果我們無法將字串轉換為非迴文，則列印“-1”。

示例

輸入

str = ‘nayan’, c = ‘n’

輸出

‘nnayan’

解釋

由於我們可以在給定字串的任何索引處插入“n”，因此可以有多個輸出字串。因此，輸出字串可以是“nnayan”、“nanyan”、“naynan”、“nayann”等。

輸入

str = ‘sss’, c = ‘s’

輸出

‘-1’

解釋

無論我們在給定字串中的哪個位置插入“s”，它都將始終是迴文。

輸入

str = ‘tutorialspoint’, c = ‘p’

輸出

‘ptutorialspoint’

解釋

由於 str 已經是非迴文，因此它透過在第一個索引處插入字元 c 來列印相同的字串。

解決上述問題的邏輯是，如果給定字串中的所有字元都等於給定的字元 c，則我們無法使其成為迴文。否則，在第一個位置新增一個字元，並檢查結果字串是否為迴文。如果是，則在末尾插入給定的字元。

方法 1

在這種方法中，我們使用 while 迴圈來檢查給定字串是否為迴文，並使用 for 迴圈來檢查給定字串中的所有字元是否相同。

演算法

• 步驟 1 - 初始化“cnt”變數以儲存等於給定字元 c 的字元的計數。

• 步驟 2 - 使用 for 迴圈遍歷字串。如果字串中第 i 個索引處的字元等於字元 c，則將“cnt”的值加 1。

• 步驟 3 - 如果“cnt”的值等於字串的長度，則列印“-1”並執行 return 語句。

• 步驟 4 - 使用 c + str 初始化“temp”變數。之後，使用 isPalindrome() 函式檢查給定字串是否為迴文。

• 步驟 5 - 定義 isPalindrome() 函式。

• 步驟 5.1 - 定義“left”變數並將其初始化為 0。同樣，定義“right”變數並將其初始化為等於字串長度 -1 的值。

• 步驟 5.2 - 使用 while 迴圈，並匹配字串開頭和結尾的字元。此外，增加“left”的值並減少“right”變數的值。

• 步驟 5.3 - 如果發現任何不匹配，則返回 false；否則，當所有迴圈迭代完成後返回 true。

• 步驟 6 - 如果“temp”變數的值是非迴文，則列印它；否則，列印 str + c。

示例

#include <bits/stdc++.h>
using namespace std;
// Function to check if a string is a palindrome
bool isPalindrome(string str) {
   int left = 0;
   int right = str.length() - 1;
   // Keep comparing characters while they are the same
   while (right > left) {
      if (str[left++] != str[right--]) {
         return false;
      }
   }
   return true;
}
// Function to make a string non-palindrome by adding a character
void makeNonPalindrome(string str, char c) {
   int cnt = 0;
   for (int i = 0; i < str.length(); i++) {
      if (str[i] == c) {
         cnt++;
      }
   }
   if (cnt == str.length()) {
      cout << "-1";
      cout << "We can convert the string into a non-palindromic string by adding a given character at any position.";
      return;
   }
   cout << "Non-palindromic string is: " << endl;
   // append the character at the start, and check if it is a palindrome
   string temp = c + str;
   if (!isPalindrome(temp)){
      cout << temp << endl;
   } else {
      cout << str + c << endl;
   }
}
int main(){
   string str = "sass";
   char c = 's';
   makeNonPalindrome(str, c);
   return 0;
}

輸出

Non-palindromic string is: 
sasss

• 時間複雜度 - O(N)，因為我們使用 for 迴圈來計算等於給定字元的字元的總數。

• 空間複雜度 - O(1)，因為我們沒有使用任何額外的空間。

方法 2

在這種方法中，我們使用了與第一個方法相同的邏輯，但我們使用 for 迴圈來檢查字串是否為迴文。此外，我們使用 count() 方法來計算字串中給定字元的總數。

演算法

• 步驟 1 - 透過將字串作為第一個引數，將給定的字元 c 作為第二個引數傳遞給 count() 方法，以計算字串中等於給定字元的字元數。

• 步驟 2 - 如果 count() 方法返回的值等於字串的長度，則列印“-1”。

• 步驟 3 - 在 isPalindrome() 函式中，將“i”初始化為 0，將“j”初始化為字串長度-1。之後，使用者使用 for 迴圈進行迭代並比較起始和結束字元。此外，如果發生任何不匹配，則返回 false。

• 步驟 4 - 在任何位置插入給定的字元，並檢查字串是否為非迴文。如果結果字串是非迴文，則我們得到了答案；否則，更改字串中給定字元的位置，並再次檢查。

示例

#include <bits/stdc++.h>
using namespace std;
// Function to check if a string is a palindrome
bool isPalindrome(string str) {
   // Start from the leftmost and rightmost corners of str
   for (int i = 0, j = str.length() - 1; i < j; i++, j--){
      // If there is a mismatch, then the string is not palindrome; return false.
      if (str[i] != str[j])
         return false;
   }
   return true;
}
// Function to make a string non-palindrome by adding a character
void makeNonPalindrome(string str, char c){
   //   if all characters are the same as a given character, then the string cannot be made non-palindrome
   if (count(str.begin(), str.end(), c) == str.length()) {
      cout << "-1";
      cout << "We can convert the string into a non-palindromic string by adding a given character at any position.";
      return;
   }
   cout << "Non-palindromic string is: " << endl;
   // append the character at the start, and check if it is a palindrome
   string temp = c + str;
   if (!isPalindrome(temp)){
      cout << temp << endl;
   } else {
      cout << c + str << endl;
   }
}
int main() {
   string str = "nayan";
   char c = 'n';
   makeNonPalindrome(str, c);
   return 0;
}

輸出

Non-palindromic string is: 
nnayan

• 時間複雜度 - O(N)

• 空間複雜度 - O(1)

結論

我們學習了兩種方法，透過在任何位置插入給定的字元將給定的字串轉換為非迴文。這兩種方法都使用相同的邏輯，但在第一種方法中，我們編寫了手動函式來計算等於給定字元的相同字元的數量，而在第二種方法中，我們使用了 count() 方法。

第一種方法更適合學習目的，第二種方法更適合即時開發。