对于给定的两个相等长度的字符串S1和S2,我们的任务是确定一个索引i,以使S1 [0…i]和S2 [i + 1…n-1]连接在一起时产生回文。已经看到,如果无法确定这样的索引,则打印-1。
S1 = “pqrsu”, S2 = “wxyqp”
输出结果
1
S1 [0..1] =“ pq”,S2 [2..n-1] =“ ypq”
S1 + S2 =“ pqyqp”表示回文。
S1 = “pqrst”, S2 = “qprqz”
输出结果
-1
首先,我们从0迭代到n(字符串的长度),并将第i个字符从S1复制到另一个字符串(假设它是S)。
之后,我们使用另一个临时字符串temp并将S2的字符从索引i +1复制到n。
最后,我们验证字符串(S + temp)是否为回文。
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Shows function that returns true if s is palindrome bool isPalindrome(string str){ int i = 0; int b = str.length() - 1; while (i< b) { if (str[i] != str[b]) return false; i++; b--; } return true; } // Shows function to return the required index int getIndex1(string S1, string S2, int n){ string S = ""; for (int i = 0; i< n; a++) { // Used to copy the ith character in S S = S + S1[i]; string temp = ""; // Used to copy all the character of string s2 in Temp for (int b = i + 1; b < n; b++) temp += S2[b]; // Verify whether the string is palindrome if (isPalindrome(S + temp)) { return i; } } return -1; } // Driver code int main(){ string S1 = "pqrsu", S2 = "wxyqp"; int n = S1.length(); cout << getIndex1(S1, S2, n); return 0; }
输出结果
1