数据结构与算法 -- 中心扩散法

不念不忘少年蓝@ 2021-10-30 04:31 216阅读 0赞

## 什么是中心扩散法？ ##

中心扩散法，顾名思义就是以某一个位置为中心，向周围扩散，直到满足条件或到达边界。

### Leetcode 5.最长回文子串 ###

题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：输入: "babad"，输出: "bab"，注意: "aba" 也是一个有效答案。

示例 2：输入: "cbbd"，输出: "bb"

解题思路：遍历s，以每个char以及两个char中点为中心，计算以此点为中心的最长回文串；

例如： 字符串abcba 共有5（字母） + 4（两字母间） = 9个中心点；因此，长度为N的string共有2N-1个中心。我们的目标就是统计以这2N-1个点为中心的最长回文串s1,s2,..,s2N-1，并从中挑出全局最长回文串。保留最大长度回文串index，记为left和right；完成遍历后返回以left和right为边界的substring

public class Solution {
        public static void main(String[] args) {
            Solution solution = new Solution();
            String s1 = "babad";
            System.out.println(solution.longestPalindrome(s1));
            String s2 = "cbbd";
            System.out.println(solution.longestPalindrome(s2));
            String s4 = "";
            System.out.println(solution.longestPalindrome(s4));
            String s3 = null;
            System.out.println(solution.longestPalindrome(s3));
        }
        public String longestPalindrome(String s) {
            if(null == s) {
                return null;
            }
            char[] charArray = s.toCharArray();
            int length = charArray.length;
            int left = 0, right = 0, longestLength = 0;
            String longestPalindromeStr = "";
            for(int i=0; i<length; i++) {
        //以单个字符为中心扩散，则有n个中心（n是输入字符串的长度）
                left = i;
                right = i;
                while(left >= 0 && right < length && charArray[left] == charArray[right]) {
                    left--;
                    right++;//cabad
                }
                if(right - left - 1 > longestLength) {
                    longestLength = right - left - 1;
                    longestPalindromeStr = s.substring(left + 1, right);
                }
            }
            for(int i=0; i<length-1; i++) {
        //以双字符为中心扩散，则有n-1个中心（n是输入字符串的长度）
                left = i;
                right = i+1;
                while(left >= 0 && right < length && charArray[left] == charArray[right]) {
                    left--;
                    right++;
                }
                if(right - left - 1 > longestLength) {
                    longestLength = right - left - 1;
                    longestPalindromeStr = s.substring(left + 1, right);
                }
            }
            return longestPalindromeStr;
        }
    }

转载于:https://www.cnblogs.com/jiangwangxiang/p/11145976.html