leetcode5.Longest Palindromic Substring

ゝ一世哀愁。 2023-03-13 03:52 3阅读 0赞

返回最长回文串

**Example 1:**

Input: "babad"
    Output: "bab"
    Note: "aba" is also a valid answer.

**Example 2:**

Input: "cbbd"
    Output: "bb"

解题思路：定义下标i,j，boolean dp\[i\]\[j\]

动态规划思想：要求大的，先求小的

1.  边界：dp\[i\]\[j\] = true
    
    1.  i ==j 单个字符一定为true
    2.  str\[i\] == str\[j\]&&j-i ==1 两个挨着的字符相等，一定为true.
2.  状态转移公式：dp\[i\]\[j\] = str\[i\] == str\[j\] && dp\[i+1\]\[j-1\]

public String longestPalindrome(String s) { 
            if (s == null || s.isEmpty()) { 
                return null;
            }
            boolean[][] mins = new boolean[s.length()][s.length()];
            int maxLen = 0;
            String maxStr = null;
            for (int len = 1; len <= s.length(); len++) { 
                for (int i = 0; i + len <= s.length(); i++) { 
                    int j = i + len - 1;
                    if (len == 1) { 
                        mins[i][j] = true;
                    } else if (len == 2) { 
                        mins[i][j] = s.charAt(i) == s.charAt(j);
                    } else { 
                        mins[i][j] = s.charAt(i) == s.charAt(j) && mins[i + 1][j - 1];
                    }
    
                    if (mins[i][j] && len > maxLen) { 
                        maxLen = len;
                        maxStr = s.substring(i, i + len);
                    }
                }
            }
            return maxStr;
    
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode5.Longest Palindromic Substring

返回最长回文串 Example 1: Input: "babad" Output: "bab" Note: "aba" is also a vali

ゝ一世哀愁。/ 2023年03月13日 03:52/ 0 赞/ 4 阅读

相关 LeetCode - Medium - 5. Longest Palindromic Substring

Topic String Dynamic Programming Description [https://leetcode.com/problems

今天药忘吃喽~/ 2022年12月31日 12:28/ 0 赞/ 127 阅读

相关 [leetcode] 5-Longest Palindromic Substring

![Center][] Palindromic Substring：回文子串，即一个字符串从左向右写和从右向走写是一样的，或者说字符串是对称。解决思路：遍历字符串，依次找

绝地灬酷狼/ 2022年09月29日 15:50/ 0 赞/ 163 阅读

相关 LeetCode--5. Longest Palindromic Substring

Problem: > Given a string S, find the longest palindromic substring in S. You may > a

骑猪看日落/ 2022年08月21日 14:58/ 0 赞/ 140 阅读

相关 leetcode 5. Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the m

清疚/ 2022年07月28日 00:25/ 0 赞/ 333 阅读

相关 LeetCode-5 Longest Palindromic Substring

Problem: Given a string S, find the longest palindromic substring in S. You may assume

你的名字/ 2022年07月26日 00:07/ 0 赞/ 178 阅读

相关 Leetcode——5. Longest Palindromic Substring

1. 概述 Given a string s, find the longest palindromic substring in s. You may assume t

柔情只为你懂/ 2022年06月15日 07:21/ 0 赞/ 178 阅读

相关 LeetCode5—Longest Palindromic Substring

本类型博客中的各算法的时间复杂度分析均为博主自己推算，本类型博客也是博主自己刷LeetCode的自己的一些总结，因此个中错误可能较多，非常欢迎各位大神在博客下方评论，请不吝赐教

偏执的太偏执、/ 2022年06月09日 13:11/ 0 赞/ 172 阅读

相关 LeetCode 5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the m

偏执的太偏执、/ 2022年05月27日 14:07/ 0 赞/ 186 阅读

相关 LeetCode 5. Longest Palindromic Substring

一、试题 Given a string s, find the longest palindromic substring in s. You may assume th

以你之姓@/ 2021年06月24日 15:57/ 0 赞/ 326 阅读