如何將字符串拆分爲儘可能少的迴文？

Question

這是一個interview question：「你給一個字符串，並希望將其分割成少數弦儘可能使得每個字符串是一個迴文」。 （我想一個一個字符的字符串被認爲是迴文，即「ABC」被分成「A」，「B」，「C」。）

你會如何回答呢？

Answer 1

首先發現所有的迴文字符串中，使得L [i] [j]表示在S [結束的第j個最長迴文的長度一世]。可以說S是輸入字符串。這可以在O（N^2）時間完成，首先考慮長1個迴文，然後長2個迴文等。 尋找長度我知道所有長度i-2迴文後，我回文是單個字符比較的問題。

這是後一個動態規劃問題。令A [i]表示Substring（S，0，i-1）可以分解成的最小回文數。

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

編輯基於Micron的請求： 這裏是背後的思想comuting 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^3）解決方案。遞歸地迭代字符串。對於每個字母，將每個迴文與這封信作爲迴文的開頭。注意奇數和偶數迴文。重複，直到字符串結束。如果在字符串末尾迴文計數最小，那麼記住你是如何到達那裏的。如果當前迴文總數和字符串中剩餘的字母大於當前迴文計數最小值，則不要進一步迭代。

的優化：當發現迴文從字符串的結尾開始，搜索您的當前字母的發生。測試子字符串爲「迴文」。不要從最短的迴文開始，這不是最優的。

Answer 3

您可以在O使用拉賓，卡普指紋識別預處理的字符串找到所有的迴文中爲O（n^2）的時間做到這一點（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 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

等效的問題是，計算串的剪斷數目。

假設你想削減使用盡可能少的剪刀的字符串，從而使每個剩餘部分本身就是一個迴文。我們將調用一個字符串的Snip Number。那就是snip數總是等於一個小於給定字符串內最小回文數的數。每個長度爲n的字符串最多有n-1個剪貼號，每個迴文的剪貼號爲0.這裏是工作的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