Longest Palindromic Substring - 字符串中最长的回文字段-阿里云开发者社区

开发者社区> 开发与运维> 正文

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 string 判断回文数,中间开花。

需求: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 string

判断回文数,中间开花。定一个中心,向两边散开。这个中心是从左到右移动的。需要2个游标。

int palindrome(String ps,int left,int right) 这个方法用来判断回文字段,返回字段长度

String longestPalindrome(String s) 在这里调用palindrome方法,遍历字符串去找。遍历过程注意不要越界。

以下为Java代码:

 1 /**
 2  * @author Rust Fisher
 3  * @date 2015-9-14
 4  */
 5 public class LongestPalindromicSubstring {
 6     /**
 7      * @param s - input string
 8      * @return the Longest Palindromic Substring 
 9      */
10     public static String longestPalindrome(String s) {
11         String result = "";
12         int inputLenght = s.length();
13         int startIndex = 0;
14         int longest = 1;
15         
16         for (int i = 0; i < inputLenght; i++) {
17             int oddLen = 1,dualLen = 1, currentLen;
18             oddLen = palindrome(s, i, i);
19             if (i+1 < inputLenght) {
20                 dualLen = palindrome(s, i, i+1);
21             }
22             currentLen = dualLen > oddLen ? dualLen : oddLen;
23             if (currentLen > longest){
24                 longest = currentLen;
25                 if (longest%2 == 0) {
26                     startIndex = i - longest/2 + 1;
27                 } else {
28                     startIndex = i - longest/2;
29                 }
30             }
31         }
32         for (int i = startIndex; i < startIndex+longest; i++) {
33             result += s.charAt(i);
34         }
35         return result;
36     }
37     /**
38      * @param ps - input string
39      * @param left - index move left
40      * @param right - index move right
41      * @return the current length of palindrome
42      */
43     public static int palindrome(String ps,int left,int right){
44         int thislen = 0;
45         int len = ps.length();
46         while(left >= 0 && right < len && ps.charAt(left) == ps.charAt(right)){
47             left--;
48             right++;
49         }
50         thislen = right - left - 1;
51         return thislen;
52     }
53     public static void main(String args[]){
54         System.out.println(longestPalindrome("hfiwafhaabbaaccddio128213"));
55         System.out.println(longestPalindrome("abcdefgfedcba"));
56         System.out.println(longestPalindrome("abc"));
57     }
58 }

输出:

aabbaa
abcdefgfedcba
a

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章