Given a binary string?s, partition the string into one or more?substrings?such that each substring is?beautiful.

A string is?beautiful?if:

• It doesn't contain leading zeros.

• It's the?binary?representation of a number that is a power of?5.

Return?the?minimum?number of substrings in such partition.?If it is impossible to partition the string?s?into beautiful substrings,?return?-1.

A?substring?is a contiguous sequence of characters in a string.

?

Example 1:

Input: s = "1011"

Output: 2

Explanation:

We can paritition the given string into ["101", "1"].?

- The string "101" does not contain leading zeros and is the binary representation of integer 51 = 5.?

- The string "1" does not contain leading zeros and is the binary representation of integer 50 = 1.?

It can be shown that 2 is the minimum number of beautiful substrings that s can be?partitioned into.

Example 2:

Input: s = "111"Output: 3

Explanation:?

We can paritition the given string into ["1", "1", "1"].

?- The string "1" does not contain leading zeros and is the binary representation of integer 50 = 1.?

It can be shown that 3 is the minimum number of beautiful substrings that s can be partitioned into.

Example 3:

Input: s = "0"

Output: -1

Explanation: We can not partition the given string into beautiful substrings.

?

Constraints:

• 1 <= s.length <= 15

• s[i]?is either?'0'?or?'1'.

Hide Hint 1

To check if number x is a power of 5 or not, we will divide x by 5 while x > 1 and x mod 5 == 0. After iteration if x == 1, then it was a power of 5.

Hide Hint 2

Since the constraint of s.length is small, we can use recursion to find all the partitions.

--------------------感覺是個(gè)經(jīng)典題目；

1：先寫一個(gè)函數(shù)判斷是否是5的冪，

2：然后去遍歷字符串，先從最長的開始，當(dāng)前數(shù)是5的冪，那么就可以去處理剩下的字符串。

剩下的字符串如果不含前導(dǎo)0，那么就返回1+當(dāng)前函數(shù)處理的字符串的長度，返回即可；

遞歸無止境，還是多學(xué)習(xí)；

Runtime:?4 ms, faster than?25.00%?of?Java?online submissions for?Partition String Into Minimum Beautiful Substrings.

Memory Usage:?42 MB, less than?25.00%?of?Java?online submissions for?Partition String Into Minimum Beautiful Substrings.