Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "how to split the text string on C++". The editor shows you the operation process through an actual case. The operation method is simple, fast and practical. I hope this article "how to split the text string on C++" can help you solve the problem.

Palindrome Partitioning split the palindrome string

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"

Output:

[

["aa", "b"]

["a", "a", "b"]

]

This is another need to use DFS to solve the problem, since the problem requires to find all the cases that may be split into palindromes, then all cases must be traversed, for each substring to determine whether it is a palindrome, then there must be a subfunction to judge palindromes, and a DFS function is needed for recursion, plus the original function, a total of three functions are needed to solve. We put the detected palindrome substring into the string array out, and when the s traversal is over, add out to the result res. So in the recursive function, we must know the current traversal position, represented by the variable start, so in the recursive function, if start is equal to the length of the string s, it means that the traversal has been completed, add out to the result res, and return. Otherwise, we will start traversing from start, because we don't know how to cut, so we have to traverse all the cuts, that is, one character, two characters, three characters, and so on. First of all, determine whether the substring is a palindrome string, and call a subfunction that determines the palindrome string. This subfunction passes the range of the start and end of the substring. If the substring is a palindrome string, we add it to out and call the recursive function. In this case, start is passed into ipalin1, and then the state of out is restored.

So, what is the access order for all substrings of the original string? if the original string is abcd, the access order is: a-> b-> c-> d-> cd- > bc-> bcd- > ab-> abc-> abcd, which is for cases where there are no two or more substrings above. If the original string is aabc, then the access order is: a-> a-> b-> c-> bc-> ab-> abc-> aa-> b-> c-> bc-> aab-> aabc. When aa is detected in the middle, it is found to be a palindrome string, so the remaining bc is detected as a new string, so there is b-> c-> bc. After scanning all the cases, the final answer can be obtained as follows:

Solution 1:

Class Solution {public: vector partition (string s) {vector res; vector out; helper (s, 0, out, res); return res;} void helper (string s, int start, vector& out, vector& res) {if (start = = s.size ()) {res.push_back (out); return;} for (int I = start; I < s.size ()) + + I) {if (! isPalindrome (s, start, I)) continue; out.push_back (s.substr (start, I-start + 1)); helper (s, I + 1, out, res); out.pop_back () }} bool isPalindrome (string s, int start, int end) {while (start < end) {if (s [start]! = s [end]) return false; + + start;-- end;} return true;}}

We can also use the original function itself instead of writing a recursive function alone. First, if the string s is empty, an array of empty strings is returned. Note that an empty array cannot be returned here, and the reason will be explained later. Then we traverse the string s from 0, because we are using the original function as recursion, so we cannot pass in the starting position start, so we can only start from the default position 0, but our input string s can be replaced by a substring, which is equivalent to the role of the starting position start. First of all, let's judge whether the substring is a palindrome string. Here, we still have to use a subfunction to judge whether the substring is a palindrome string. Since the starting point is always 0, we only need to pass a destination position. If the substring is a palindrome string, the recursive function is called on the whole part of the following string, so we get a two-dimensional array, which is all the cases of the palindrome string split into the whole part after the current substring. Then we just need to add the current palindrome substring to the set of all cases returned. Now explain why an array with an empty array is returned when the string s is empty. This is because when the substring is the original string s, but is still a palindrome string, then the latter part is empty. If we call an empty array recursively on the empty string, it cannot be traversed, and the current palindrome string cannot be added to the result res. See the code below:

Solution 2:

Class Solution {public: vector partition (string s) {vector res; if (s.empty ()) return {{}}; for (int I = 0; I < s.size (); + + I) {if (! isPalindrome (s, I + 1)) continue For (auto list: partition (s.substr (I + 1) {list.insert (list.begin (), s.substr (0, I + 1)); res.push_back (list);} return res;} bool isPalindrome (string s, int n) {for (int I = 0; I < n / 2) + + I) {if (s [I]! = s [n-1-I]) return false;} return true;}}

The following solution is based on the optimization of solution 1. We can first establish the dp array of the substring palindromes of the string s, and this part alone can create another Palindromic Substrings. When we establish such a two-dimensional array dp, where dp [I] [j] indicates whether the substrings in the range of [I, j] are palindromes, there is no need for another subfunction to judge whether the substrings are palindromes. It greatly improves the efficiency of calculation, isn't it beautiful? The writing of the recursive function is no different from that in solution 1. You can take a look at the previous explanation. See the code below:

Solution 3:

Class Solution {public: vector partition (string s) {int n = s.size (); vector res; vector out; vector dp (n, vector (n)); for (int I = 0; I < n; + I) {for (int j = 0; j)

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.