Come dividere una stringa nel minor numero possibile di palindromi?

Question

Questo è un interview question: "Viene assegnata una stringa e si desidera suddividerla nel minor numero possibile di stringhe in modo che ogni stringa sia un palindromo". (Immagino che una stringa di caratteri sia considerata un palindromo, cioè "abc" è divisa in "a", "b", "c".)

Come risponderesti?

Answer 1

Prima trovare tutti i palindromi nella stringa tale che L [i] [j] rappresenta la lunghezza del palindromo più lungo j-esimo che termina a S [ io]. Diciamo che S è la stringa di input. Questo potrebbe essere fatto nel tempo O (N^2) considerando prima i palindromi di lunghezza 1 poi i palindromi di lunghezza 2 e così via. Trovare i palindromi di Length i dopo aver conosciuto tutti i palindromi i-2 di una lunghezza è questione di un confronto di un singolo carattere.

Questo è un problema di programmazione dinamica dopo quello. Sia A [i] rappresenti il ​​più piccolo numero di palindromi in cui è possibile scomporre la sottostringa (S, 0, i-1).

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

Edit in base alla richiesta di Micron: Ecco l'idea che sta dietro comuting L [i] [j]. Ho appena scritto questo per trasmettere l'idea, il codice potrebbe avere problemi.

// 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^3) soluzione. Ripetere la stringa in modo ricorsivo. Per ogni lettera stabilisci ogni palindromo con questa lettera come inizio del palindromo. Presta attenzione ai palindromi con numeri dispari e pari. Ripeti fino alla fine della stringa. Se alla fine della stringa il conteggio del palindromo è minimo, ricorda come ci sei arrivato. Non eseguire un'iterazione ulteriore se la somma dei conteggi palindromi correnti e le lettere rimanenti nella stringa sono maggiori del conteggio minimo del palindromo corrente.

Un'ottimizzazione: quando palindromi scoperta partono dalla fine della stringa e la ricerca per il verificarsi di vostra lettera corrente. Prova la sottostringa a "palindromness". Non iniziare da palindromi più brevi, non è ottimale.

Answer 3

È possibile eseguire questa operazione in tempo O (n^2) utilizzando il fingerprinting Rabin-Karp per preelaborare la stringa per trovare tutti i palindromi in O (n^2). Dopo la pre-elaborazione, si esegue il codice simile al seguente:

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 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

Un problema equivalente è quella di calcolare il numero Snip di una stringa.

si supponga di voler tagliare una stringa utilizzando il minor numero di tagli, in modo che ogni pezzo rimanente in sé un palindromo è stato. Il numero di tali tagli chiameremo il numero di snip di una stringa. Quello è il numero di snip sempre uguale a uno in meno del numero più piccolo di palindromi all'interno di una determinata stringa. Ogni stringa di lunghezza n ha il numero di snip al massimo n-1, e ciascun palindromo ha uno snip numero 0. Qui sta lavorando codice Python.

             
  
 
   
 
    
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