计算将字符串拆分为至少具有 1 个元音的 X 部分的可能性

Count number of possibilities to split a string into X parts with at least 1 vowel

提问人：Tomek Swiecki 提问时间：10/21/2023 更新时间：10/21/2023 访问量：51

问：

您将获得一个文本（最多 100 个字符），需要将单词分成 X 个部分，每个部分至少包含 1 个元音。

输入中给出了 X。

例如，对于以下文本：bcaeiouxtz 和 x = 3，我们有 6 种可能性：

BCA EIO UXTZ

BCA ei ouxtz

BCA e IOUXTZ

BCAE IO UXTZ

BCAE i ouxtz

BCAEI o UXTZ

我想写动态编程方法，在这种方法中，我将能够计算出我可以拥有多少种可能性。

任何帮助将不胜感激，谢谢！

算法 子字符串

评论

2赞 Gassa 10/21/2023
组合解决方案也存在。但是动态规划也应该没问题。但是，您必须更具体地提出问题。具体来说，您寻求什么帮助？
0赞 Tomek Swiecki 10/21/2023
所以你基本上在输入中得到一个字符串 a 和一个整数 x。您要回答的问题是，您可以通过多少种方式将字符串分成 x 个部分，以便每个部分至少有一个元音。这些部分必须是 s 的非空子字符串。
1赞 Abhinav Mathur 10/21/2023
你能添加你到目前为止尝试过的任何方法吗？表明您可能已经努力解决问题？
0赞 Tomek Swiecki 10/21/2023
我尝试解决 x = 2 和元音数 <=3 的问题。x = 2 的解决方案很简单，你只需要看看是否可以将任何字符串一分为二，并查询每个部分是否有元音，这可以使用前缀总和来完成。对于元音数 = 1，没有解决方案。对于元音 = 2，您必须查看第一个元音和最后一个元音之间有多少个字母。对于元音 = 3，您必须将第一个元音和第二个元音之间的字母数量乘以第二个元音和最后一个元音之间的字母数量。这就是我目前得到的。

答： 暂无答案

上一个：AAA Recursion_Count

下一个：在 R 中快速高效地提取和比较子字符串