这不是家庭作业,虽然它可能看起来像.我一直在浏览英国计算机奥林匹克的网站,发现了这个问题(问题1):这里.我对它感到困惑,我想看看你们怎么想的怎么做.我想不出有任何简洁的方法可以把所有东西分成小组(在它之后检查它是否是回文很简单,即originalString == new String(groupedString.Reverse.SelectMany(c => c).ToArray)假设它是一个char数组).
有任何想法吗？谢谢!
工作人员的文字:
回文是一个在反转时显示相同字母序列的单词.如果一个单词可以将其字母组合在两个或多个块中(每个块包含一个或多个相邻的字母),那么如果颠倒这些块的顺序导致相同的块序列,则它是块回文.
例如,使用括号表示块,以下是块回文:
•BONBON可以组合在一起(BON)(BON);
•ONION可以组合在一起(ON)(I)(ON);
•BBACBB可以组合在一起为(B)(BACB)(B)或(BB)(AC)(BB)或(B)(B)(AC)(B)(B)
注意,(BB)(AC)(B)(B)无效,因为反向(B)(B)(AC)(BB)以不同的顺序示出了块.
问题本质上是如何生成所有这些组,然后检查它们是否是回文!
问题本质上是如何生成所有这些组,然后检查它们是否是回文!
我注意到这不一定是最好的策略.首先生成所有组然后检查它们是否是palidromes比仅生成回收组的效率要低得多.
但是,本着回答问题的精神,让我们递归地解决问题.我将生成所有组; 检查一组组是否是回文,留作练习.我也将忽略一组包含至少两个元素的要求; 这很容易检查.
优雅地解决这个问题的方法是递归地推理.与所有递归解决方案一样,我们从一个简单的基础案例开始:
空字符串有多少个分组？只有空的分组; 也就是说,没有元素的分组.
现在我们假设我们有一个解决较小问题的解决方案,并问"如果我们有一个解决较小问题的解决方案,我们如何使用该解决方案来解决更大的问题？"
好吧,假设我们遇到了更大的问题.我们有一个包含6个字符的字符串,我们希望生成所有分组.而且,分组是对称的; 第一组与最后一组的大小相同.假设我们知道如何解决任何较小字符串的问题.
我们解决问题如下.假设字符串是ABCDEF.我们从两端剥离A和F,我们解决了BCDE的问题,记住我们知道如何通过假设来做,现在我们预先添加A并将F附加到每个解决方案中.
BCDE的解决方案是(B)(C)(D)(E), (B)(CD)(E), (BC)(DE), (BCDE).同样,我们假设我们有归纳假设,我们可以解决较小的问题.然后,我们将这些与A和F结合起来,为ABCDEF制作解决方案: (A)(B)(C)(D)(E)(F), (A)(B)(CD)(E)(F), (A)(BC)(DE)(F)和(A)(BCDE)(F).
我们取得了很好的进展.我们完了吗？不.接下来我们剥离AB和EF,并递归地解决CD的问题.我不会这样做.我们完了吗？不.我们剥离ABC和DEF并递归地解决中间空字符串的问题.我们完了吗？不.(ABCDEF)也是一种解决方案.现在我们完成了.
我希望草图能够激发解决方案,现在这个解决方案很简单.我们从辅助函数开始:
public static IEnumerable<T> AffixSequence<T>(T first, IEnumerable<T> body, T last)
{
yield return first;
foreach (T item in body)
yield return item;
yield return last;
}
这应该很容易理解.现在我们做真正的工作:
public static IEnumerable<IEnumerable<string>> GenerateBlocks(string s)
{
// The base case is trivial: the blocks of the empty string
// is the empty set of blocks.
if (s.Length == 0)
{
yield return new string[0];
yield break;
}
// Generate all the sequences for the middle;
// combine them with all possible prefixes and suffixes.
for (int i = 1; s.Length >= 2 * i; ++i)
{
string prefix = s.Substring(0, i);
string suffix = s.Substring(s.Length - i, i);
string middle = s.Substring(i, s.Length - 2 * i);
foreach (var body in GenerateBlocks(middle))
yield return AffixSequence(prefix, body, suffix);
}
// Finally, the set of blocks that contains only this string
// is a solution.
yield return new[] { s };
}
我们来试试吧.
foreach (var blocks in GenerateBlocks("ABCDEF"))
Console.WriteLine($"({string.Join(")(", blocks)})");
输出是
(A)(B)(C)(D)(E)(F)
(A)(B)(CD)(E)(F)
(A)(BC)(DE)(F)
(A)(BCDE)(F)
(AB)(C)(D)(EF)
(AB)(CD)(EF)
(ABC)(DEF)
(ABCDEF)
你去吧
您现在可以检查每个分组是否是回文,但为什么？如果前缀和后缀不相等,则可以通过简单地不递归来轻松修改上述算法以消除所有非回文:
if (prefix != suffix) continue;
该算法现在只列举块回文.我们来测试一下:
foreach (var blocks in GenerateBlocks("BBACBB"))
Console.WriteLine($"({string.Join(")(", blocks)})");
输出低于; 再次注意,我没有过滤掉"整个字符串"块,但这样做很简单.
(B)(B)(AC)(B)(B)
(B)(BACB)(B)
(BB)(AC)(BB)
(BBACBB)
如果您对此主题感兴趣,请考虑阅读我使用相同技术生成每个可能的树形拓扑和语言中每个可能的字符串的系列文章.它从这里开始:
http://blogs.msdn.com/b/ericlippert/archive/2010/04/19/every-binary-tree-there-is.aspx