数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究通过插入给定字符使字符串非回文
问题陈述
输入中给定一个字符串 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() 方法。
第一种方法更适合学习目的，第二种方法更适合实时开发。
90 次浏览
