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

 

什么是中心扩散法?

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

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;
    }
}

 

上一篇:区块链去中心化DAPP系统开发智能合约软件系统定制开发公司


下一篇:区块链以太坊DApp开发实战(一)——基础知识