問題陳述
我們在輸入中給出了字符串 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()方法。
第一種方法更適合學習目的,第二種方法更適合實時開發。
以上就是通過插入給定字符使字符串變為非回文的詳細內容,更多請關注www.xfxf.net其它相關文章!