Как разбить строку на как можно меньше палиндромов?

Question

Это вопрос для интервью : «Вам дана строка, и вы хотите разбить ее на как можно меньшее количество строк, чтобы каждая строка была палиндромом». (Я предполагаю, что одна символьная строка считается палиндромом, то есть «abc» разбивается на «a», «b», «c».)

Как бы вы ответили?

Answer 1

Сначала найдите все палиндромы в строке, так что L [i] [j] представляет длину j-го самого длинного палиндрома, который заканчивается в S [i].Допустим, S является входной строкой.Это можно сделать за O (N ^ 2), сначала рассмотрев палиндромы длины 1, затем палиндромы длины 2 и так далее.Поиск длины i палиндромов после того, как вы знаете всю длину i-2 палиндромов, это вопрос сравнения одного символа.

Это проблема динамического программирования после этого.Пусть A [i] представляет наименьшее число палиндромов, на которое может быть разложена подстрока (S, 0, i-1).

A[i+1] = min_{0 <= j < length(L[i])} A[i - L[i][j]] + 1;

Редактирование на основе запроса Микрона: Вот идея, лежащая в основе вычисления L [i] [j].Я просто написал это, чтобы передать идею, код может иметь проблемы.

// Every single char is palindrome so L[i][0] = 1;
vector<vector<int> > L(S.length(), vector<int>(1,1));

for (i = 0; i < S.length(); i++) {
 for (j = 2; j < S.length; j++) {
   if (i - j + 1 >= 0 && S[i] == S[i-j + 1]) {
     // See if there was a palindrome of length j - 2 ending at S[i-1]
     bool inner_palindrome = false;
     if (j ==2) {
      inner_palindrome = true;
     } else {
       int k = L[i-1].length;
       if (L[i-1][k-1] == j-2 || (k >= 2 && L[i-1][k-2] == j-2)) {
         inner_palindrome = true;
       }
     }
     if (inner_palindrome) {
       L[i].push_back(j);
     }
   } 
 }
} 

Answer 2

Вы можете сделать это за O (n ^ 2) время, используя отпечатки пальцев Рабина-Карпа, чтобы предварительно обработать строку, чтобы найти все палиндромы за O (n ^ 2) времени. После предварительной обработки вы запускаете код, подобный следующему:

np(string s) {
  int a[s.size() + 1];
  a[s.size()] = 0;
  for (int i = s.size() - 1; i >= 0; i--) {
    a[i] = s.size() - i;
    for (int j = i + 1; j <= s.size(); j++) {
      if (is_palindrome(substr(s, i, j))) // test costs O(1) after preprocessing
        a[i] = min(a[i], 1 + a[j]);
  }
  return a[0];
}

Answer 3

Эквивалентной проблемой является вычисление номера строки Snip.

Предположим, что вы хотите вырезать строку, используя наименьшее количество фрагментов, чтобы каждый оставшийся фрагмент был самим палиндромом.Количество таких срезов мы будем называть Snip Number строки.То есть число фрагментов всегда равно на единицу меньше, чем наименьшее количество палиндромов в данной строке.Каждая строка длины n имеет номер фрагмента не более n-1, а каждый палиндром имеет номер фрагмента 0. Вот рабочий код Python.

<div class="snippet" data-lang="js" data-hide="false">
<div class="snippet-code">
<pre class="snippet-code-html lang-html prettyprint-override"><code>def snip_number(str):
    n=len(str)
 
 #initialize Opt Table
 # Opt[i,j] = min number of snips in the substring str[i...j]
 
    Opt=[[0 for i in range(n)] for j in range(n) ]
 
 #Opt of single char is 0
    for i in range(n):
     Opt[i][i] = 0
 
 #Opt for adjacent chars is 1 if different, 0 otherwise
    for i in range(n-1):
     Opt[i][i+1]= 1 if str[i]!=str[i+1] else 0
 
 
# we now define sil as (s)substring (i)interval (l) length of the
# interval [i,j] --- sil=(j-i +1) and j = i+sil-1
 
# we compute Opt table entry for each sil length and
# starting index i
 
    for sil in range(3, n+1):
     for i in range(n-sil+1):
       j = i+sil-1
       if (str[i] == str[j] and Opt[i+1][j-1]==0):
         Opt[i][j] = 0
       else:
         snip= min( [(Opt[i][t]+ Opt[t+1][j] + 1 ) for t in range(i,j-1)])
         Opt[i][j] = snip

    return Opt[0][len(str)-1]
#end function snip_number()
mystr=[""for i in range(4)]         
mystr[0]="abc"
mystr[1]="ohiho"
mystr[2]="cabacdbabdc"
mystr[3]="amanaplanacanalpanama aibohphobia "


for i in range(4):
     print mystr[i], "has snip number:", snip_number(mystr[i])
     
# abc has snip number: 2
# ohiho has snip number: 0
# cabacdbabdc has snip number: 2
# amanaplanacanalpanama aibohphobia  has snip number: 1

Answer 4

bool ispalindrome(string inp)
{
    if(inp == "" || inp.length() == 1)
    {
        return true;
    }
    string rev = inp;

    reverse(rev.begin(), rev.end());

    return (rev == inp);
}

int minsplit_count(string inp)
{
    if(ispalindrome(inp))
    {
        return 0;
    }

    int count= inp.length();

    for(int i = 1; i < inp.length(); i++)
    {
        count = min(count, 
                      minsplit_count(inp.substr(0, i))              + 
                      minsplit_count(inp.substr(i, inp.size() - i)) + 
                      1);
    }

    return count;
}

Answer 5

O (n ^ 3) решение.Итерация строки рекурсивно.Для каждой буквы установите каждый палиндром с этой буквой в качестве начала палиндрома.Обратите внимание на нечетные и четные палиндромы.Повторяйте до конца строки.Если в конце строки число палиндромов минимально, помните, как вы туда попали.Не выполняйте итерации, если сумма текущего числа палиндромов и оставшихся букв в строке больше минимального значения текущего числа палиндромов.

Оптимизация: при обнаружении палиндромов начинайте с конца строки и ищите вхождениятекущее письмо.Проверьте подстроку на «палиндромность».Не начинайте с самых коротких палиндромов, это не оптимально.