5.Longest Palindromic Substring:修订间差异

来自WHY42
Riguz留言 | 贡献
Riguz留言 | 贡献
第108行: 第108行:
</syntaxhighlight>
</syntaxhighlight>


== Two Pointers==
{{Submission|runtime=5ms|memory=40.92MB|rp=99.44|mp=90.23}}
<syntaxhighlight lang="java">
class Solution {
    private int start;
    private int max;
    public String longestPalindrome(String s) {
        if(s.length() < 2) return s;
        start = 0;
        max = 0;
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length; i++){
            findPalindrome(chars, i, i);
            findPalindrome(chars, i, i+1);
        }
        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:LeetCode]]
[[Category:LeetCode]]

2023年9月24日 (日) 15:54的版本

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 {
    private int start;
    private int max;

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

        start = 0;
        max = 0;
        char[] chars = s.toCharArray();

        for(int i = 0; i < chars.length; i++){
            findPalindrome(chars, i, i);
            findPalindrome(chars, i, i+1);
        }
        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;
        }
    } 
}