Skip to content

Latest commit

 

History

History
89 lines (59 loc) · 1.86 KB

2478-number-of-beautiful-partitions.adoc

File metadata and controls

89 lines (59 loc) · 1.86 KB

2478. Number of Beautiful Partitions

{leetcode}/problems/number-of-beautiful-partitions/[LeetCode - 2478. Number of Beautiful Partitions ^]

You are given a string s that consists of the digits '1' to '9' and two integers k and minLength.

A partition of s is called beautiful if:

  • s is partitioned into k non-intersecting substrings.

  • Each substring has a length of at least minLength.

  • Each substring starts with a prime digit and ends with a non-prime digit. Prime digits are '2', '3', '5', and '7', and the rest of the digits are non-prime.

Return_ the number of beautiful partitions of _`s`. Since the answer may be very large, return it modulo 109 + 7.

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

Example 1:

Input: s = "23542185131", k = 3, minLength = 2
Output: 3
Explanation: There exists three ways to create a beautiful partition:
"2354 | 218 | 5131"
"2354 | 21851 | 31"
"2354218 | 51 | 31"

Example 2:

Input: s = "23542185131", k = 3, minLength = 3
Output: 1
Explanation: There exists one way to create a beautiful partition: "2354 | 218 | 5131".

Example 3:

Input: s = "3312958", k = 3, minLength = 1
Output: 1
Explanation: There exists one way to create a beautiful partition: "331 | 29 | 58".

Constraints:

  • 1 ⇐ k, minLength ⇐ s.length ⇐ 1000

  • s consists of the digits '1' to '9'.

思路分析

一刷
link:{sourcedir}/_2478_NumberOfBeautifulPartitions.java[role=include]

参考资料