NC17 最长回文子串

た入场券 2024-03-27 17:06 77阅读 0赞

> [牛客华为机试题库【题号 HJ开头】（重点看）][HJ]  
> [牛客在线编程算法篇【题号NC开头】][NC]  
> [剑指offer【题号 JZ开头】][offer_ JZ]  
> [力扣][Link 1]

### 1）[原题链接][Link 2] ###

### 2）已有题解 ###

### 3）代码 ###

package src.main.java.doublepoint;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    
    import static java.lang.System.in;
    
    /**
     * NC17 最长回文子串
     */
    public class NC17LongestPalindrome {
        
        public static void main(String[] args) throws IOException {
        
            BufferedReader bf = new BufferedReader(new InputStreamReader(in));
            String str = bf.readLine();
            bf.close();
    
            int longestPalindrome = getLongestPalindrome(str);
            System.out.println(longestPalindrome);
        }
    
        public static int getLongestPalindrome(String A) {
        
            int max = 0;
    
            int len = A.length();
            //暴力解法
            for (int i = 0; i < len; i++) {
        
                for (int j = i + 1; j <= len; j++) {
        
                    String subStr = A.substring(i, j);//确定字符
                    if (isPalindrome(subStr) && subStr.length() > max) {
        
                        max = subStr.length();//最大长度
                    }
                }
            }
    
            return max;
        }
    
        /**
         * 判断子串是不是回文子串
         */
        public static boolean isPalindrome(String s) {
        
            // abcba  奇数时 5/2=2 范围for (int i = 0; i < 2; i++) [0 1] 2 3 4
            // abccba 偶数时 6/2=3 范围for (int i = 0; i < 3; i++) [0 1 2] 3 4 5
            int strLength = s.length();
            for (int i = 0; i < strLength / 2; i++) {
        
                // 数组折叠对应下标相加为strLength - 1
                if (s.charAt(i) != s.charAt(strLength - 1 - i))//不相等
                    return false;
            }
            return true;
        }
    }

[HJ]: https://www.nowcoder.com/exam/oj/ta?tpId=37
[NC]: https://www.nowcoder.com/exam/oj
[offer_ JZ]: https://www.nowcoder.com/exam/oj/ta?page=1&tpId=13&type=13
[Link 1]: https://leetcode.cn/problemset/all/
[Link 2]: https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=196&tqId=37122&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=/exam/oj?page=1&pageSize=50&search=NC17&tab=%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587&topicId=196&difficulty=undefined&judgeStatus=undefined&tags=&title=NC17