5.Longest Palindromic Substring:修订间差异

来自WHY42
Riguz留言 | 贡献
Created page with "=Description= {{LeetCode |id=longest-palindromic-substring |no=5 |difficulty=Medium |category=Dynamic Programming |collection=Top 150 |title=Longest Palindromic Substring |summary=Given a string s, return the longest palindromic substring in s.}} Example 1: <syntaxhighlight lang="java"> Input: s = "babad" Output: "bab" </syntaxhighlight> Explanation: "aba" is also a valid answer. Example 2: <syntaxhighlight lang="java"> Input: s = "cbbd" Output: "bb" </syntaxhighlig..."
 
Riguz留言 | 贡献
 
(未显示同一用户的4个中间版本)
第24行: 第24行:
Output: "bb"
Output: "bb"
</syntaxhighlight>
</syntaxhighlight>
=Solution=
=Solution=
==2D DP==
==2D DP==
第62行: 第63行:
</syntaxhighlight>
</syntaxhighlight>


优化后:


{{Submission|runtime=197ms|memory=55.77MB|rp=19.59|mp=5.03}}
<syntaxhighlight lang="java">
class Solution {
    public String longestPalindrome(String s) {
        /**
            s= babad
            1 0 1 0 0 bab
            # 1 0 1 0 aba
            # # 1 0 0
            # # # 1 0
            # # # # 1
        */
        int [][] dp = new int[s.length()][s.length()];
        for(int[] temp: dp)
            Arrays.fill(temp, -1);
        int max=1, start=0, end=0;
        for(int k = 1; k <= s.length(); k++){
            for(int i = 0; i < s.length(); i++) {
                int j = i + k - 1;
                if(j >= s.length())
                    break;
                if(i == j) dp[i][j] = 1;
                else if(s.charAt(i)  == s.charAt(j)){
                    dp[i][j] = i + 1 > j -1 || dp[i+1][j-1] == 1 ? 1: 0;
                    if(dp[i][j] == 1 && k > max) {
                        start = i;
                        end = j;
                        max = k;
                    }
                } else dp[i][j] = 0;
            }
        }
        // for(int i = 0; i < s.length(); i++) {
        //    for(int j = 0; j < s.length(); j++) {
        //        System.out.print(dp[i][j] == -1? "#": dp[i][j]);
        //        System.out.print(" ");
        //    }
        //    System.out.println();
        // }
        return s.substring(start, end + 1);
    }
}
</syntaxhighlight>
== Two Pointers==
{{Submission|runtime=5ms|memory=40.92MB|rp=99.44|mp=90.23}}
<syntaxhighlight lang="java">
class Solution {
    /* https://leetcode.com/problems/longest-palindromic-substring/solutions/4001583/simple-and-best-solution/ */
    private int start;  // 起始位置
    private int max;    // 最大长度
    public String longestPalindrome(String s) {
        if(s.length() < 2) return s;
        start = 0;
        max = 0;
        // toCharArray 比charAt少了边界检查,会更快一些
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length; i++){
            findPalindrome(chars, i, i);    // 以i为中心,奇数长度
            findPalindrome(chars, i, i+1);  // 以i为中心,偶数长度
        }
        return s.substring(start, start + max);
    }
    private void findPalindrome(char[] chars, int i, int j) {
        while(i >= 0 && j < chars.length && chars[i] == chars[j]){
            i--;
            j++;
        }
        int len = j - i - 1;
        if(len > max) {
            max = len;
            start = i + 1;
        }
    }
}
</syntaxhighlight>
[[Category:Algorithm]]
[[Category:Algorithm]]
[[Category:Dynamic Programming]]
[[Category:Dynamic Programming]]
[[Category:Two Pointers]]
[[Category:LeetCode]]
[[Category:LeetCode]]

2023年10月7日 (六) 13:40的最新版本

Description

#5 Longest Palindromic Substring Medium
Dynamic Programming Top 150
Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"

Explanation: "aba" is also a valid answer.


Example 2:

Input: s = "cbbd"
Output: "bb"

Solution

2D DP

Runtime 291ms
Memory 55.82MB
class Solution {
    private int[][] dp;
    private String s;
    public String longestPalindrome(String s) {
        this.s = s;
        this.dp = new int[s.length()][s.length()];
        for(int[] temp: dp)
            Arrays.fill(temp, -1);

        int max = 1, start = 0, end = 0;
        for(int i = 0; i < s.length(); i++) {
            for(int j = i+1; j < s.length(); j++) {
                if(isPalindromic(i, j) && (j - i + 1 > max)) {
                    max = j - i + 1;
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start, end+1);
    }

    private boolean isPalindromic(int start, int end) {
        if(start >= end)
            return true;
        if(dp[start][end] != -1)
            return dp[start][end] == 1;
        boolean isPalindromic = (s.charAt(start) == s.charAt(end)) && isPalindromic(start+1, end -1); 
        dp[start][end] =  isPalindromic ? 1: 0;
        return isPalindromic;
    }
}

优化后:

Runtime 197ms
Memory 55.77MB
class Solution {
    public String longestPalindrome(String s) {
        /**
            s= babad
            1 0 1 0 0 bab
            # 1 0 1 0 aba
            # # 1 0 0 
            # # # 1 0 
            # # # # 1
         */
        int [][] dp = new int[s.length()][s.length()];
        for(int[] temp: dp)
            Arrays.fill(temp, -1);
        int max=1, start=0, end=0;
        for(int k = 1; k <= s.length(); k++){
            for(int i = 0; i < s.length(); i++) {
                int j = i + k - 1;
                if(j >= s.length())
                    break;
                if(i == j) dp[i][j] = 1;
                else if(s.charAt(i)  == s.charAt(j)){
                    dp[i][j] = i + 1 > j -1 || dp[i+1][j-1] == 1 ? 1: 0;
                    if(dp[i][j] == 1 && k > max) {
                        start = i;
                        end = j;
                        max = k;
                    }
                } else dp[i][j] = 0;
            }
        }
        // for(int i = 0; i < s.length(); i++) {
        //     for(int j = 0; j < s.length(); j++) {
        //         System.out.print(dp[i][j] == -1? "#": dp[i][j]);
        //         System.out.print(" ");
        //     }
        //     System.out.println();
        // }
        return s.substring(start, end + 1);
    }
}

Two Pointers

Runtime 5ms
Memory 40.92MB
class Solution {
    /* https://leetcode.com/problems/longest-palindromic-substring/solutions/4001583/simple-and-best-solution/ */
    private int start;  // 起始位置
    private int max;    // 最大长度

    public String longestPalindrome(String s) {
        if(s.length() < 2) return s;

        start = 0;
        max = 0;
        // toCharArray 比charAt少了边界检查,会更快一些
        char[] chars = s.toCharArray();

        for(int i = 0; i < chars.length; i++){
            findPalindrome(chars, i, i);    // 以i为中心,奇数长度
            findPalindrome(chars, i, i+1);  // 以i为中心,偶数长度
        }
        return s.substring(start, start + max);
    }

    private void findPalindrome(char[] chars, int i, int j) {
        while(i >= 0 && j < chars.length && chars[i] == chars[j]){
            i--;
            j++;
        }
        int len = j - i - 1;
        if(len > max) {
            max = len;
            start = i + 1;
        }
    } 
}