用C++编写程序将两个字符串拆分成回文

如果字符串在反转后保持不变,则称该字符串为回文字符串。

在这个特殊问题中,我们给出了两个长度相同的字符串 'a' 和 'b'。如果它们被一些索引分割,那么任务是检查字符串的总和是否构成回文。

假设我们有两个长度为 '4' 的字符串 'a' 和 'b' 并且在将两个字符串拆分为索引 '3' 之后,

                 啊| b  和bbb | 一种

aaa(第一个字符串的前缀)+a(suffix of second string)应该是回文

要么

b(suffix of first string)+bbb(prefix of second string)应该是回文

例如

输入-1: 

a = “abcdef”b = “fedcba”

输出:

True

说明: 在索引 '2' 处拆分字符串 'a' 和字符串 'b' 后,它们将变成,

ABC | def 和美联储 | 工商银行

这样abc(prefix of first string)+cba(suffix of second string)就构成了一个回文字符串。因此我们将返回“True”。

输入 2: 

a =  “eatable”b =  “tableau”

输出:

False

说明: 没有可能的方法使这两个字符串成为回文。

解决这个问题的方法

为了解决这个特殊问题,我们将使用双指针方法。在这种方法中,首先,我们将初始化两个指针,low 和 high,这样 low 指向 '0',high 指向字符串的最后一个字符。

由于两个字符串的长度相等,我们将检查它们中的任何一个是否少于 2 个字符。如果是,我们将返回 True。否则,我们将通过在指针的帮助下遍历整个字符串来递归检查。如果两个字符串相等,则返回 True,否则返回 False。

  • 取两个字符串,分别为 'a' 和 'b'。

  • 布尔函数checkPalindromic(string a, string b)将两个字符串作为输入参数,并相应地返回 True 或 False。

  • 初始化两个指针,low 和 high,low = 0,high = 字符串 'b' 的长度。

  • 遍历字符串并检查两个字符串的字符是否相等。

  • 布尔函数split(string a, string b)接受两个字符串,如果它们是回文则返回 True,否则返回 False。

示例

#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string a, int low, int high) {
   while (low < high) {
      if (a[low] != a[high])
         return false;
      low++;
      high--;
   }
   return true;
}
bool Split(string a, string b) {
   int low = 0;
   int high = b.size() - 1;
   while (low < high and a[low] == b[high]) {
      low++;
      high--;
   }
   return isPalindrome(a, low, high) || isPalindrome(b, low, high);
}
bool checkPalindromic(string a, string b) {
   if (a.size() < 2)
      return true;
   return Split(a, b) || Split(b, a);
}
int main() {
   string a = "abcpqr";
   string b = "mnocba";
   if (checkPalindromic(a, b)) {
      cout << "True" << endl;
   } else {
      cout << "False" << endl;
   }
   return 0;
}

运行上面的代码将生成输出,

输出结果

True

说明: 如果我们在索引 '2' 处拆分给定的字符串 'abcpqr' 和 'mnocba' 使得,

a(prefix)= abc      b(suffix)= cba

a(suffix)= pqr  和  b(prefix)= mno

我们可以观察到a(prefix)+b(suffix)是一个回文,因此输出为 True。