very simple java solution using one-dimensional dp


  • 0
    F

    refer to https://en.wikipedia.org/wiki/Longest_common_substring_problem for detailed information and here is my java code:

    public String longestPalindrome(String s) {
            String t = new StringBuilder(s).reverse().toString();
            int n = s.length(), maxLen = 0, to = 0;
            int[] dp = new int[n + 1];
            for (int i = 0; i < n; i++) {
                char ch1 = s.charAt(i);
                for (int j = n; j > 0; j--) {
                    char ch2 = t.charAt(j - 1);
                    if (ch1 == ch2) {
                        dp[j] = dp[j - 1] + 1;
                        if (maxLen <= dp[j]) {
                            maxLen = dp[j];
                            to = j;
                        }
                    } else {
                        dp[j] = 0;
                    }
                }
            }
            return t.substring(to - maxLen, to);
        }

  • 0
    P

    This is a O(n^2) complexity solution


  • 1
    F

    yes, time complexity is n^2, but space complexity is n


  • 0
    P

    you can get a better solution by using Manacher's algo. O(N) time and N space


  • 0
    F

    could you share your solution please


  • 0
    P

    This is a very descriptive solution... Please give a positive rep if you like the solution.

    follow the 2nd solution. O(n)time and space


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.