current position:Home>LeetCode Algorithm Question 5 - Longest Palindrome Substring

LeetCode Algorithm Question 5 - Longest Palindrome Substring

2022-11-24 22:39:33I'm crazy

要求:

给你一个字符串 s,找到 s 中最长的回文子串.个字符串 s,找到 s 中最长的回文子串

最终没有通过 :

String s="aacabdkacaa";

This test cardbug!

package com.zhm.test;

/**
 * @Author bige
 * @Date: 2022/11/18 20:03
 * @ApiNote:给你一个字符串 s,找到 s 中最长的回文子串.Palindrome substring means:read the same,The same goes for reverse reading.
 */
public class Leatcode_test005 {
    public static String longestPalindrome(String s) {
        String sub="";
        int flag=-1;
        if(s.trim()!=""){
            for (int i = 0; i < s.length(); i++) {
                System.out.println("===================================i="+i);
                if(s.indexOf(s.charAt(i)) != s.lastIndexOf(s.charAt(i))){
                    int first = s.indexOf(s.charAt(i));
                    int last = s.lastIndexOf(s.charAt(i));

                    //System.out.println("first_num="+(first));
                    //System.out.println("last_num="+(last));
                    if((last-first)>2){//(6-0)/2=3
                        for (int j = 0; j < ((last-first)/2); j++) {
                            System.out.println("first="+(first+j+1));
                            System.out.println("last="+(last-j-1));
                            System.out.println("first_num="+s.charAt(first+j+1));
                            System.out.println("last_num="+s.charAt(last-j-1));
                            if(s.charAt(first+j+1) == s.charAt(last-j-1)){
                                System.out.println("这是回文!");
                                flag=1;
                            }else{
                                System.out.println("这是错误!");
                                flag=0;
                                break;
                            }
                        }
                        if(!(flag==0)){
                            sub=s.substring(first,last+1);
                            return sub;
                        }
                    }else {
                        //System.out.println("这是回文!i="+i);
                        sub=s.substring(first,last+1);
                        return sub;
                    }
                }else {
                    if(s.length()==1){
                        return s;
                    }else if(s.length()==2){
                        return s.substring(0,1);
                    }
                }
            }
        }
        return sub;
    }

    public static void main(String[] args) {

        //String s ="asftyubcacbad";
        //String s ="axsdccccc";
        //String s ="cbbd";
        //String s="ac";
        String s="aacabdkacaa";
        //longestPalindrome(s);
        System.out.println("result="+longestPalindrome(s));
    }
}

My approach does have many flaws,Test data failed.Going to use another algorithm.

第二种办法:

Let's sort out our thinking first:

1.We iterate over all strings.Each letter is used for comparison.

2.while traversing each letter,Go to the left and right for comparison.

如下图所示:当索引为3时,字母为a. Then look to the left=b , Query to the right=b . And it does not exceed the boundary, it is regarded as a palindrome. 

贴上代码:

package com.zhm.test;

/**
 * @Author bige
 * @Date: 2022/11/18 20:03
 * @ApiNote:给你一个字符串 s,找到 s 中最长的回文子串.Palindrome substring means:read the same,The same goes for reverse reading.
 */
public class Leatcode_test005 {
    public static String longestPalindrome1(String s) {
        String sub="";
        int flag=-1;
        if(s.trim()!=""){
            for (int i = 0; i < s.length(); i++) {
                System.out.println("===================================i="+i);
                if(s.indexOf(s.charAt(i)) != s.lastIndexOf(s.charAt(i))){
                    int first = s.indexOf(s.charAt(i));
                    int last = s.lastIndexOf(s.charAt(i));

                    //System.out.println("first_num="+(first));
                    //System.out.println("last_num="+(last));
                    if((last-first)>2){//(6-0)/2=3
                        for (int j = 0; j < ((last-first)/2); j++) {
                            System.out.println("first="+(first+j+1));
                            System.out.println("last="+(last-j-1));
                            System.out.println("first_num="+s.charAt(first+j+1));
                            System.out.println("last_num="+s.charAt(last-j-1));
                            if(s.charAt(first+j+1) == s.charAt(last-j-1)){
                                System.out.println("这是回文!");
                                flag=1;
                            }else{
                                System.out.println("这是错误!");
                                flag=0;
                                break;
                            }
                        }
                        if(!(flag==0)){
                            sub=s.substring(first,last+1);
                            return sub;
                        }
                    }else {
                        //System.out.println("这是回文!i="+i);
                        sub=s.substring(first,last+1);
                        return sub;
                    }
                }else {
                    if(s.length()==1){
                        return s;
                    }else if(s.length()==2){
                        return s.substring(0,1);
                    }
                }
            }
        }
        return sub;
    }

    public static String longestPalindrome(String s) {
        String res = new String();//指向结果
        for(int i = 0; i < s.length(); i++){//遍历字符串,Take the current character as the center character in turn
            for(int j = 0; j <= 1; j++){//j = 0, single center,j = 1两个中心
                int l = i, r = i + j;//左右指针
                while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
                    if(res.length() < r - l + 1){//Update the current substring
                        res = s.substring(l, r + 1);//截取子串,左闭右开
                    }
                    l--;
                    r++;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {

        //String s ="asftyubcacbad";
        //String s ="axsdccccc";
        //String s ="cbbd";
        //String s="ac";
        String s="aacabdkacaa";
        //longestPalindrome(s);
        System.out.println("result="+longestPalindrome(s));
    }
}

代码效果:

copyright notice
author[I'm crazy],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/328/202211242224316438.html

Random recommended