Comment diviser une chaîne en aussi peu de palindromes que possible?

Question

Ceci est un interview question: "Vous recevez une chaîne, et vous voulez la diviser en aussi peu de chaînes que possible, de sorte que chaque chaîne soit un palindrome". (Je suppose qu'une chaîne de caractères est considérée comme un palindrome, c'est-à-dire que "abc" est divisé en "a", "b", "c".)

Comment y répondriez-vous?

Answer 1

d'abord trouver tous les palindromes dans la chaîne tel que L [i] [j] représente la longueur du j-ième plus long palindrome qui se termine à S [ je]. Disons que S est la chaîne d'entrée. Ceci pourrait être fait en temps O (N^2) en considérant d'abord les palindromes de longueur1 puis les palindromes de longueur 2 et ainsi de suite. Trouver la longueur i palindromes après que vous connaissez toutes les longueurs palindromes i-2 est la question d'une comparaison de caractères unique.

Ceci est un problème de programmation dynamique par la suite. Soit A [i] représente le plus petit nombre de palindrome dans lequel la sous-chaîne (S, 0, i-1) peut être décomposée.

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

Modifier basé sur la demande de Micron: Voici l'idée derrière comuting L [i] [j]. Je viens d'écrire ceci pour transmettre l'idée, le code peut avoir des problèmes.

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

Solution O (n^3). Itérer la chaîne récursivement. Pour chaque lettre, établissez chaque palindrome avec cette lettre comme le début du palindrome. Faites attention aux palindromes pairs et impairs. Répétez jusqu'à la fin de la chaîne. Si à la fin de la chaîne le nombre de palindrome est minime, alors rappelez-vous comment vous y êtes arrivé. Ne pas itérer davantage si la somme des palindromes actuels compte et si les lettres restantes dans la chaîne sont plus grandes que le nombre actuel de palindromes.

Une optimisation: lors de la découverte de palindromes, commencez à partir de la fin de la chaîne et recherchez l'occurrence de votre lettre actuelle. Testez la sous-chaîne à "palindromness". Ne commencez pas par les palindromes les plus courts, ce n'est pas optimal.

Answer 3

Vous pouvez le faire en temps O (n^2) en utilisant les empreintes Rabin-Karp pour prétraiter la chaîne pour trouver tous les palindromes en temps O (n^2). Après le pré-traitement, vous exécutez un code similaire à ce qui suit:

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 autre problème est que l'équivalent de calculer le nombre Snip d'une chaîne. Supposons que vous vouliez couper une chaîne en utilisant le moins de cisailles, de sorte que chaque pièce restante soit elle-même un palindrome. Le nombre de ces coupes sera appelé le Snip Number d'une chaîne. C'est le nombre de snip est toujours égal à un de moins que le plus petit nombre de palindromes dans une chaîne donnée. Chaque chaîne de longueur n a un nombre de snip au plus n-1, et chaque palindrome a un numéro de snip 0. Voici un code python qui fonctionne.

             
  
 
   
 
    
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