透過插入給定字元使字串變為非回文

問題陳述

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

範例

輸入

str = ‘nayan’, c = ‘n’

輸出

‘nnayan’

Explanation

的翻譯為：

解釋

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

輸入

str = ‘sss’, c = ‘s’

輸出

‘-1’

Explanation

的翻譯為：

解釋

無論我們在給定的字串中插入“s”的位置如何，它總是一個回文。

輸入

str = ‘tutorialspoint’, c = ‘p’

輸出

‘ptutorialspoint’

Explanation

的翻譯為：

解釋

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

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

方法一

在這種方法中，我們使用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。

Example

的中文翻譯為：

範例

#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 - 使用count() 方法，將字串作為第一個參數傳遞，給定字元c 作為第二個參數來計算等於給定字元的字元數在字串中。

• 第二步 - 如果count()方法傳回的值等於字串的長度，則列印「-1」。

• 步驟 3 - 在isPalindrome()函數中，將‘i’初始化為0，將‘j’初始化為字串的長度-1。之後，使用者使用循環進行迭代並比較起始和結束字元。如果出現任何不匹配，則返回false。

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

Example

的中文翻譯為：

範例

#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()方法。

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

以上是透過插入給定字元使字串變為非回文的詳細內容。更多資訊請關注PHP中文網其他相關文章！