【LeetCode OJ 005】Longest Palindromic Substring
1356 ワード
タイトルリンク: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であり、文字列の真ん中から両側の文字が同じであることが特徴である.文字列の2番目の文字から左と右に同時にスキャンし、文字長が最も長い文字列を見つけることができます.サンプルコードは次のとおりです.
タイトル: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であり、文字列の真ん中から両側の文字が同じであることが特徴である.文字列の2番目の文字から左と右に同時にスキャンし、文字長が最も長い文字列を見つけることができます.サンプルコードは次のとおりです.
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);
}