使用动态编程求解leetcode“ 5.最长的alindromic substring”
#编程 #编码 #java #算法

类型:媒介

问题:
给定一个字符串s,返回最长的
s中的alindromic substring。

示例1:
输入:s = "babad"
输出:"bab"
说明:"aba" is also a valid answer.

示例2:
输入:s = "cbbd"
输出:"bb"

约束:

1 <= s.length <= 1000
s consist of only digits and English letters.

方法:

初始化:
该代码初始化了两个私有整数变量,即启动和长度,以跟踪找到最长的alindromic substring的起始索引和长度。最初,两个都设置为0。

最长的核心方法:
定义了一种名为LINGESTPALINDROME的公共方法,该方法采用一个参数,输入字符串S,并返回最长的Palindromic Substring。

边缘案例检查:
该方法首先检查输入字符串S的长度是否为0或1。如果是这些情况中的任何一个,则直接返回字符串本身,因为单个字符或空字符串被视为palindrome。

通过字符串迭代:
a for循环通过字符串s的字符迭代。变量i表示潜在的palindrome的当前中心。

重文检查:
在循环内,代码调用palindromechecker方法两次:
首先,它称palindromechecker(i,i,s)检查了我是中心字符的奇数palindromes。
然后,它调用palindromechecker(i,i,i + 1,s)检查均匀的palindromes,其中i和i + 1代表均匀的palindromes的两个中心字符。

palindromechecker方法:
这种私人方法负责检查给定的指针(左右指针)是否在中心周围扩展时会形成文明。
它使用一个段循环检查左Pointer和右pointer的字符是否相同,并且指针是否在字符串的范围内。
如果它们是相同的,则意味着可以扩展palindrome,因此左POINTER向左移动一步(减少),右Pointer向右移动一个步骤(增量)。

更新最长的回文:

在段环退出后,这意味着palindrome的扩展已经停止,要么是因为左pointer距左侧太远,右pointer太远了,或者发现了一个特征不匹配。

>

该方法然后检查当前的palindrome的长度(从左POINTER到右Pointer)是否大于先前记录的最长腔(长度变量)的长度。
如果更长,则它更新为leftPointer + 1(当前的palindrome的开始索引)和长度为rightpointer -lewpointer -1(当前palindrome的长度)。

返回结果:
在处理字符串中的所有潜在中心之后,最长的核心方法返回使用使用substring()方法启动和启动 +长度索引找到的最长的圆柱源性子字符串。

总而言之,该代码有效地通过使用中心扩展方法在给定的字符串中找到了最长的alindromic substring。它保持了开始和长度变量,以跟踪此过程中最长的腔植物。该方法可确保检查所有可能的回文,并在结果中返回最长的回文。

代码:


public class Solution {
    private int start = 0;
    private int length = 0;
    public String longestPalindrome(String s) {
        if (s.length() == 1 || s.length() == 0)
            return s;

        for (int i = 0; i < s.length() - 1; i++) {
            palindromeChecker(i, i, s);
            palindromeChecker(i, i + 1, s);
        }

        return s.substring(start, start + length);
    }

    private void palindromeChecker(int leftPointer, int rightPointer, String s) {
        while (leftPointer >= 0 && rightPointer < s.length() && s.charAt(leftPointer) == s.charAt(rightPointer)) {
            leftPointer--;
            rightPointer++;
        }
        if (length < rightPointer - leftPointer - 1) {
            start = leftPointer + 1;
            length = rightPointer - leftPointer - 1;
        }
    }
}

愉快的编码,
湿婆