您的位置:js12345金沙官网登入 > 网络编程 > 005. Longest Palindromic Substringjs12345金沙官网登入

005. Longest Palindromic Substringjs12345金沙官网登入

2019-10-08 04:59

如果 [0, k] match [j, j + k]k >= s.length() && j < s.length()之后将这个字符串取出来。s.substring 就会越界。因为 s 的指针都跑到reverse 去找匹配了,并且还找到了,导致长度比实际长度还要长。所以我们需要用 # 强行隔开两者。

方法4:

方法3类似,对于某个字符,以它为中心扩展出一个palindrome(长度为奇数)。再以它和它右边的字符一起为中心,扩展出一个palindrome(长度为偶数)。每次都选取其中最长的一个。

这样,当我们遍历所有可能的字符,并以它们为中心去扩展出palindrome,其中最长的那个就是最终的结果。

代码如下:

class Solution
{
public:
    string longestPalindrome(string s)
    {
        int n = s.size();
        if (n < 2)
        {
            return s;
        }

        int maxLen = 0;
        int begin = 0;
        for (int i = n / 2, j = i + 1; (2 * i + 2 > maxLen || 2 * (n - j) - 2 > maxLen);)
        {
            if (2 * i + 2 > maxLen)  // 找出以i或(i, i + 1)为中心的最长palindrome。
            {
                auto range = longestPalindromeWithCenter(s, i--);
                auto len = range.second - range.first + 1;
                if (len > maxLen)
                {
                    maxLen = len;
                    begin = range.first;
                }
            }

            if (2 * (n - j) - 2 > maxLen)  // 找出以j或(j, j + 1)为中心的最长palindrome。
            {
                auto range = longestPalindromeWithCenter(s, j++);
                auto len = range.second - range.first + 1;
                if (len > maxLen)
                {
                    maxLen = len;
                    begin = range.first;
                }
            }
        }
        return s.substr(begin, maxLen);
    }

private:
    // 找出以pos或(pos, pos + 1)为中心的最长palindrome,返回它首尾字符的下标。
    pair<int, int> longestPalindromeWithCenter(const string &s, int pos)
    {
        auto res = make_pair(0, -1);
        for (int i = pos, j = pos; i >= 0 && j < s.size(); i--, j++)  // 以pos为中心,长度是奇数。
        {
            if (s[i] != s[j])
            {
                break;
            }
            else if (j - i > res.second - res.first)
            {
                res = {i, j};
            }
        }

        for (int i = pos, j = pos + 1; i >= 0 && j < s.size(); i--, j++)  // 以(pos, pos + 1)为中心,长度为偶数。
        {
            if (s[i] != s[j])
            {
                break;
            }
            else if (j - i > res.second - res.first)
            {
                res = {i, j};
            }
        }
        return res;
    }
};

这道题目搞了很久。终于看了答案自己写了出来。首先做了下 implement strStr() 题,复习了下 KMP算法终于记起来怎么写了,希望下次不要忘记。。。

方法1:

从左到右遍历每一个字符,然后针对这个字符,从右向左找出它可能对应的回文子串,并记住最长的子串。

代码如下:

class Solution
{
public:
    string longestPalindrome(string s)
    {
        char *head = nullptr;
        char *tail = nullptr;
        for (int i = 0; i + len(head, tail) < s.size(); i++)
        {
            for (int j = s.size(); j > i + len(head, tail); j--)
            {
                if (s[j] == s[i] && isPalindrome(&s[i], &s[j]))
                {
                    head = &s[i];
                    tail = &s[j];
                    break;
                }
            }
        }
        return string(head, len(head, tail));
    }

private:
    bool isPalindrome(const char *head, const char *tail)
    {
        while (head < tail)
        {
            if (*head != *tail)
            {
                return false;
            }
        }
        return true;
    }

    inline int len(const char *head, const char *tail)
    {
        return (head == nullptr || tail == nullptr) ? 0 : (tail - head + 1);
    }
};

但是这个答案是不被LeetCode接受的,因为超时。上面的算法时间复杂度是:O(n^3),需要提高其效率。


| ------> | # | <------ |012345 543210所以如果 dp[len - 1] = 2表示,有两位 prefix match with postfix即, s[0, 1] 是最长回文字符串。然后我们拿到这个长度,把之后的string拿出来reverse,加在前面。这道题目就解决了。

解题思路:

KMP 文章:http://blog.csdn.net/v_july_v/article/details/7041827

题目:

Given a string S, find the longest palindromic substring in S.

You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.


然后这道题目,可以继续抽象。找到 以 index = 0 开头的substring,是最长的palindrome找到之后,将剩余的部分反转,加在前面,就行了。

方法2:动态规划。

假设字符串长度为n,我们准备一个二维数组dp[n][n]。
用下面的规则来处理dp:

  • 只使用矩阵的右上一半。
  • 处理顺序是从下到上,而每一行中则是从左到右。
  • 对于dp[i][j]:
    • 如果 j - i < 2 && s[i] == s[j],则s[js12345金沙官网登入,i, j]为回文子串,记dp[i][j] = 1。
    • 如果 j - i >= 2 && s[i] == s[j] && dp[i+1][j-1],则s[i, j]为回文子串,记dp[i][j] = 1。

代码如下:

class Solution
{
public:
    string longestPalindrome(string s)
    {
        auto dp = createDp(s.size());
        int head = 0;
        int tail = -1;  // 为了使长度(tail - head + 1)恰好为0。

        for (int i = s.size() - 1; i >= 0; i--)
        {
            for (int j = i; j < s.size(); j++)
            {
                if ((j - i < 2 && s[i] == s[j])
                    || (j - i >= 2 && s[i] == s[j] && dp[i + 1][j - 1] == 1))
                {
                    dp[i][j] = 1;
                    if (len(i, j) > len(head, tail))
                    {
                        head = i;
                        tail = j;
                    }
                }
            }
        }
        return s.substr(head, len(head, tail));
    }

private:
    vector<vector<int>> createDp(int n)
    {
        vector<vector<int>> dp(n);
        for (auto &x : dp)
        {
            x = vector<int>(n);
        }
        return dp;
    }

    inline int len(int head, int tail)
    {
        return (tail - head + 1);
    }
};

这个方法的时间复杂度是:O(n2),空间复杂度也是:O(n2)。可是LeetCode仍然不接受,说是内存占用太多(尝试了把dp所占空间减少一半,仍然不被接受)。


reference:https://discuss.leetcode.com/topic/27261/clean-kmp-solution-with-super-detailed-explanation/2

方法3:

假设有字符串:abcba,我们先构造如下字符串:#a#b#c#b#a#,即在每个字符的前后添加一个特殊字符。然后进行以下处理:

从最中间的那个字符开始,找出以它为中心的最长的palindrome,记为longest

如果左边有可能找到更长的palindrome,那就以mid - 1为中心去找palindorme。如果它的确更长,就更新longest

如果右边有可能找到更长的palindrome,那就以mid + 1为中心去找palindrome。如果它的确更长,就更新longest

如果左边(或右边)仍然有可能找到更长的palindrome,那就以更左(或更右)的元素为中心,去找palindrome。直到左右都不可能找到更长的。

最后,把longest中的特殊符号('#')去掉。

代码如下:

class Solution
{
public:
    string longestPalindrome(string s)
    {
        s = addSeperator(s);
        string longest;
        for (int i = s.size() / 2, j = i + 1; i >= 0 || j < s.size(); i--, j++)
        {
            if (2 * i + 1 > longest.size())  // 如果以i为中心有可能找到更长的palindrome
            {
                auto palindrome1 = findPalindrome(s, i);
                if (palindrome1.size() > longest.size())
                {
                    longest = palindrome1;
                }
            }

            if (2 * (s.size() - j) - 1 > longest.size())  // 如果以j为中心有可能找出更长的palindrome
            {
                auto palindrome2 = findPalindrome(s, j);
                if (palindrome2.size() > longest.size())
                {
                    longest = palindrome2;
                }
            }
        }

        return removeSeperator(longest);
    }

private:
    string& addSeperator(string &s, char sep = '#')  // "abc" ==> "#a#b#c#"
    {
        auto n = s.size();
        for (int i = 0; i <= n; i++)
        {
            s.insert(i * 2, 1, sep);
        }
        return s;
    }

    string& removeSeperator(string &s)  // "#a#b#c#" ==> "abc"
    {
        int n = s.size();
        for (int i = 0; i < n / 2 + 1; i++)
        {
            s.erase(i, 1);
        }
        return s;
    }

    string findPalindrome(const string &s, int mid)  // find a palindrome whose center is mid.
    {
        int left = mid - 1;
        int right = mid + 1;
        while (left >= 0 && right < s.size() && s[left] == s[right])
        {
            left--;
            right++;
        }

        left++;
        right--;
        return s.substr(left, right - left + 1);
    }
};

时间复杂度O(n^2),空间复杂度O(n)。


下面的问题是,如果找到这个最长的palindrome.

本文由js12345金沙官网登入发布于网络编程,转载请注明出处:005. Longest Palindromic Substringjs12345金沙官网登入

关键词: