如何分割字符串成尽可能少的回文的可能吗？ [英] How to split a string into as few palindromes as possible?

问题描述

这是一个<一个href="http://www.glassdoor.com/Interview/You-re-given-a-string-and-you-want-to-split-it-into-as-few-strings-as-possible-such-that-each-string-is-a-palindrome-QTN_114464.htm">interview问题：你给一个字符串，并且希望将它拆分成尽可能少的字符串作为可能使得每个字符串是一个回文。 （我想一个一个字符的字符串被认为是一个回文，即ABC被分成A，B，C。）

This is an interview question: "You're given a string, and you want to split it into as few strings as possible such that each string is a palindrome". (I guess a one char string is considered a palindrome, i.e. "abc" is split into "a", "b", "c".)

你会如何回答呢？

推荐答案

首先找到字符串中的所有回文使得L [i] [j]的重presents的第j个最长的回文，在结束长S [1]。可以说，S是输入字符串。这可能为O首先考虑然后再长2回文等长度1回文完成（N ^ 2）的时间。 查找长度我回文你知道所有的长度后，I-2回文是一个字符比较的问题。

First find all the palindromes in the string such that L[i][j] represents the length of j-th longest palindrome that ends at S[i]. Lets say S is the input string. This could be done in O(N^2) time by first considering length1 palindromes then then length 2 palindromes and so on. Finding Length i palindromes after you know all length i-2 palindromes is the matter of a single character comparison.

这是后一个动态规划问题。设A [i]于重新present最小数目回文那个子串（S，O，I-1）可以被分解成的。

This is a dynamic programming problem after that. Let A[i] represent the smallest number of palindrome that Substring(S,0,i-1) can be decomposed into.

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

基于美光的要求编辑： 这背后是comuting L [i] [j]的想法。我只是写了这件事传达的理念，code可能有问题。

Edit based on Micron's request: Here is the idea behind comuting L[i][j]. I just wrote this up to convey the idea, the code may have problems.

// 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);
     }
   } 
 }
} 

这篇关于如何分割字符串成尽可能少的回文的可能吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！