找到索引i,使S1的前缀和S2的后缀直到在C ++中串联时形成回文

概念

对于给定的两个相等长度的字符串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
猜你喜欢