algorithm - 将两个字符串分开形成回文

Question

给定两个长度相等的字符串 A 和 B，找出是否可以在公共(public)点处切割两个字符串，使得 A 的第一部分和 B 的第二部分形成回文。我试过蛮力，这可以在 O(N^2) 中实现。我正在寻找任何类型的优化。我不熟悉反向跟踪和 DP。那么，任何人都可以提出一些建议......我是否应该在这些方面思考？

Answer 1

这是一个可能的解决方案，考虑到我们将 2 个字符串剪切到一个公共(public)点。它以线性时间 w.r.t 字符串长度运行，因此在 O(n) 中。

// Palindrome function
function is_pal(str) {
  str_len = len(str)
  result = true
  for i from 0 to 1 + str_len / 2 {
    if str[i] != str[str_len - i] then {
      result = false
      break
    }
  }
  return result
}
// first phase: iterate on both strings
function solve_pb(A, B) {
  str_len = len(A)
  idx = 0
  while A[idx] == B[str_len - idx - 1] {
    idx += 1
  }
  if idx >= str_len / 2 {
    return str_len / 2
  else if is_pal(A[idx + 1 ... str_len - idx - 2]) {
    return str_len - idx - 2
  else if is_pal(B[idx + 1 ... str_len - idx - 2]) {
    return idx
  else
    return -1 // no solution possible

原理如下:
首先，我们对 A 进行迭代，然后对 B 进行反向迭代，只要它们是“对称的”即可。

A: aaabcaabb   ............    // ->  
B: ............   bbaacbaaa    // <-  

如果字符串在它们各自的中间之前是对称的，那么解决方案是微不足道的。否则，我们检查 A 或 B 的“中间部分”本身是否为回文。如果是这种情况我们有解决方案，否则我们没有解决方案。