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

This article mainly introduces "how to write code to achieve the longest substring of a string". In daily operation, I believe many people have doubts about how to write code to achieve the longest substring of a string. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubt of "how to write code to achieve the longest substring of a string". Next, please follow the editor to study!

/ * @ author pxu * @ create 2021-4-7-2:28 afternoon * / public class Nc017 {public static void main (String [] args) {String str = "abc1234321ab"; Nc017 nc017 = new Nc017 (); int longestPalindrome = nc017.getLongestPalindrome (str, str.length ()); System.out.println (longestPalindrome) } public int getLongestPalindrome (String A, int n) {/ * this problem uses a top-down dynamic programming method to solve the problem of the longest palindromic subsequence of string A. * transformed into three sub-problems: finding the solutions of A.sutString (1MagneA. Length), A.sutString (0MagneA. Futhmae1) * and A.sutString (1MagneA.Summer1), and comparing the solutions of the three cases, we get the optimal solution * * first verify the validity of the parameters, and define a two-dimensional array to record the solutions of the subproblems that have been solved. The main solving process * in the helper method * / switch (n) {case 0: return 0 Case 1: return 1; default: {Optimum [] [] dp = new Optimum [n] [n]; Optimum optimum = helper (A, dp, 0, n-1); return optimum.len } public Optimum helper (String theStr, Optimum [] [] solArr, int start, int end) {/ * the final result returned by this method * / Optimum res = null / * invalid parameters directly return null * / if (start=solArr.length | | start > end) return null Else {/ * if the result of the current sub-problem has been obtained, directly return the result recorded in dp * / if (solArr [start] [end]! = null) {return solArr [start] [end] } else if (start = = end) {/ * is used to handle the case of an one-character substring * / res = new Optimum (start,end,theStr) } else {/ * respectively solve the optimal solution of the three sub-problems * / Optimum left = helper (theStr, solArr, start + 1, end); Optimum right = helper (theStr, solArr, start, end-1) Optimum mid = helper (theStr, solArr, start + 1, end-1) / * if the characters in the start position and the end position are equal Then the solution to the A.sutString type problem * needs to be further processed * / if (theStr.charAt (start) = = theStr.charAt (end)) {/ * if start and end are adjacent integers, such as 6 and 7 Then you can know from the above code that mid must be null at this time, * but the characters in the start position and end position are equal, then the mid solution should be a palindrome string of length 2. * * if mid is not null, and the starting and ending position of the palindrome string of mid solution happens to be adjacent to start and end, then the solution * can be further extended to include the characters in start and end positions. * / if (mid = = null | | (mid.start = = start+1 & & mid.end = = end-1) mid = new Optimum (start,end,theStr);} / * * compare and get the optimal solution * / Optimum finest = left If (middie null & & mid.len > finest.len) finest = mid; if (rightfully null & right.len > finest.len) finest = right; res = finest }} / * the optimal solution of this subproblem is recorded in the array * / solArr [start] [end] = res; / * return solution * / return res }} class Optimum {/ * this class represents the longest palindrome substring of a substring of the original string * @ param start the starting offset of this palindrome string in the original string * @ param end the termination offset of this palindrome string in the original string * @ param len the length of this palindrome string * @ param str this palindrome string itself * / int start = 0 Int end= 0; int len=-1; String str= "; @ Override public String toString () {return" Solution {"+" start= "+ start +", end= "+ end +", len= "+ len +", str=' "+ str +'\'+'}' } public Optimum () {} public Optimum (int start, int end, String oriStr) {this.start = start; this.end = end; this.len = end-start+1; this.str = oriStr.substring (start,end+1);} at this point, the study on "how to write code to implement the longest palindrome substring of a string" is over, hoping to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.