number-of-beautiful-partitions

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a string <code>s</code> that consists of the digits <code>&#39;1&#39;</code> to <code>&#39;9&#39;</code> and two integers <code>k</code> and <code>minLength</code>.

A partition of <code>s</code> is called beautiful if:

<ul>
	<li><code>s</code> is partitioned into <code>k</code> non-intersecting substrings.</li>
	<li>Each substring has a length of at least <code>minLength</code>.</li>
	<li>Each substring starts with a prime digit and ends with a non-prime digit. Prime digits are <code>&#39;2&#39;</code>, <code>&#39;3&#39;</code>, <code>&#39;5&#39;</code>, and <code>&#39;7&#39;</code>, and the rest of the digits are non-prime.</li>
</ul>

Return the number of beautiful partitions of <code>s</code>. Since the answer may be very large, return it modulo <code>109 + 7</code>.

A substring is a contiguous sequence of characters within a string.

&nbsp;
Example 1:

<pre>
Input: s = &quot;23542185131&quot;, k = 3, minLength = 2
Output: 3
Explanation: There exists three ways to create a beautiful partition:
&quot;2354 | 218 | 5131&quot;
&quot;2354 | 21851 | 31&quot;
&quot;2354218 | 51 | 31&quot;
</pre>

Example 2:

<pre>
Input: s = &quot;23542185131&quot;, k = 3, minLength = 3
Output: 1
Explanation: There exists one way to create a beautiful partition: &quot;2354 | 218 | 5131&quot;.
</pre>

Example 3:

<pre>
Input: s = &quot;3312958&quot;, k = 3, minLength = 1
Output: 1
Explanation: There exists one way to create a beautiful partition: &quot;331 | 29 | 58&quot;.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= k, minLength &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consists of the digits <code>&#39;1&#39;</code> to <code>&#39;9&#39;</code>.</li>
</ul>

beautifulPartitions

Number of Beautiful Partitions

Restore The Array

restore-the-array

恢复数组

Number of Ways to Separate Numbers

number-of-ways-to-separate-numbers

划分数字的方案数

String

Dynamic Programming

给你一个字符串&nbsp;<code>s</code>&nbsp;，每个字符是数字&nbsp;<code>'1'</code>&nbsp;到&nbsp;<code>'9'</code>&nbsp;，再给你两个整数&nbsp;<code>k</code> 和&nbsp;<code>minLength</code>&nbsp;。

如果对 <code>s</code>&nbsp;的分割满足以下条件，那么我们认为它是一个 完美&nbsp;分割：

<ul>
	<li><code>s</code>&nbsp;被分成 <code>k</code>&nbsp;段互不相交的子字符串。</li>
	<li>每个子字符串长度都 至少&nbsp;为&nbsp;<code>minLength</code>&nbsp;。</li>
	<li>每个子字符串的第一个字符都是一个 质数 数字，最后一个字符都是一个 非质数&nbsp;数字。质数数字为&nbsp;<code>'2'</code>&nbsp;，<code>'3'</code>&nbsp;，<code>'5'</code>&nbsp;和&nbsp;<code>'7'</code>&nbsp;，剩下的都是非质数数字。</li>
</ul>

请你返回 <code>s</code>&nbsp;的 完美&nbsp;分割数目。由于答案可能很大，请返回答案对&nbsp;<code>109 + 7</code>&nbsp;取余&nbsp;后的结果。

一个 子字符串&nbsp;是字符串中一段连续字符串序列。

&nbsp;

示例 1：

<pre>
输入：s = "23542185131", k = 3, minLength = 2
输出：3
解释：存在 3 种完美分割方案：
"2354 | 218 | 5131"
"2354 | 21851 | 31"
"2354218 | 51 | 31"
</pre>

示例 2：

<pre>
输入：s = "23542185131", k = 3, minLength = 3
输出：1
解释：存在一种完美分割方案："2354 | 218 | 5131" 。
</pre>

示例 3：

<pre>
输入：s = "3312958", k = 3, minLength = 1
输出：1
解释：存在一种完美分割方案："331 | 29 | 58" 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= k, minLength &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code>&nbsp;每个字符都为数字&nbsp;<code>'1'</code>&nbsp;到&nbsp;<code>'9'</code> 之一。</li>
</ul>