Разделите две строки, чтобы сформировать палиндром - PullRequest
Новая
       16

Разделите две строки, чтобы сформировать палиндром

0 голосов
/ 22 мая 2019

Учитывая две строки, A и B, равной длины, найдите, можно ли обрезать обе строки в общей точке, так что первая часть A и вторая часть B образуют палиндром.Я пробовал брутфорс, это может быть достигнуто в O (N ^ 2).Я ищу любой вид оптимизации.Я не знаком с отслеживанием спины и DP.Итак, кто-нибудь может пролить некоторый свет ... я должен думать в этих строках?

1 Ответ

1 голос
/ 22 мая 2019

Вот возможное решение, учитывая, что мы обрезаем 2 строки в общей точке. Он работает за линейное время с длиной строки, поэтому в 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 палиндромом. Если это так, у нас есть решение, в противном случае у нас нет решения.

...