Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to solve the problem of segmenting the text string by Java". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "Java how to solve the problem of segmenting the text string"!

Title

Give a string s, and split s so that each substring is a palindrome string.

Calculate the minimum number of cuts that split the string s into palindromes

For example: given string s = "aab"

Return 1, because the palindrome segmentation result ["aa", "b"] is generated by cutting once.

Train of thought analysis

First of all, it is known that the length of the string s is len, so if you want to require the first len string to be cut into a palindrome string, you will naturally think of the minimum number of cuts needed to cut the string formed by the first I characters into the palindrome string, that is, state F (I).

Then, it occurs to you that the maximum number of splits required to convert a string formed by the first I characters into a palindrome string is iMur1. For example, the string "aab" cuts 2 knives to form palindromes "a", "a", "b" of length 1.

Then, the key lies in the process of solving the minimum number of cuts, where violent solution is adopted to define the variable j so that it is less than I. In the case where we know the state F (j) (that is, the minimum number of cuts for the string formed by the first j characters), if [jwatches 1J] is a palindrome string, then the last knife can find the minimum number of cuts currently used. Then F (I) = min (F (I), F (j) + 1), which means that the number of segmentation of the first I string obtained last time is compared with the number of times obtained this time, and the minimum value is taken. (note: [jafa1jue I] here refers to the meaning of the j + 1 character to the I character of the string, not the subscript index of the string. When writing the code, the conversion to the index should be to find out whether the string formed from the character with the subscript jmur1 to the character with the subscript I is a palindrome string)

Then, to implement the method to determine whether it is a palindrome string, the simple idea is to provide the string s for the method, and provide the start subscript start and the end subscript end,start of the substring.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.