通过插入给定字符使字符串变为非回文

问题陈述

我们在输入中给出了字符串 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中文网其他相关文章！