【LeetCode OJ】Longest Palindromic Substring

题目链接：https://leetcode.com/problems/longest-palindromic-substring/

题目：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.

解题思路：palindromic-substring是指回文串，例如abba、abcba，它有一个特点就是从字符串的中间开始往两边的字符都是一样的。我们可以从字符串的第二个字符开始向左边和右边同时扫描，找到字符长度最长的回文串。示例代码如下：

public class Solution

{

    public String longestPalindrome(String s)

    {

          int n = s.length();

          if (n <= 1)

              return s;

         int maxlen = 1, k, j, a = 0;

         int l;

         for (int i = 1; i < n;)

         {

            k = i - 1;

            j = i + 1;

            //扫描左边与s[i]相同的字符

            while (k >= 0 && s.charAt(k) == s.charAt(i))

                  k--;

            //扫描右边与是s[i]相同的字符

            while (j < n && s.charAt(j) == s.charAt(i))

                    j++;

            while (k >= 0 && j < n && s.charAt(k) == s.charAt(j))

            {

                k--;

                j++;

            }

            l = j - k - 1;

            if (maxlen < l)

            {

                a = k + 1;

                maxlen = l;

            }

            i++;

         }

          return s.substring(a, a+maxlen);

    }

巴特西

【LeetCode OJ】Longest Palindromic Substring

最新文章

热门文章