背景:
所谓对称子字符串,就是这个子字符串要么是以其中一个词对称:比如 “aba”, “abcba”;要么就完全对称:比如"abba", "abccba"。
问题:
给你一个字符串,找出该字符串中对称的子字符串的最大长度。
思路:
首先,我们用字符数组 char[] array 来保持这个字符串,假设现在已经遍历到第 i 个字符,要找出以该字符为“中心”的最长对称字符串,我们需要用另两个指针分别向前和向后移动,直到指针到达字符串两端或者两个指针所指的字符不相等。因为对称子字符串有两种情况,所以需要写出两种情况下的代码:
1. 第 i 个字符是该对称字符串的真正的中心,也就是说该对称字符串以第 i 个字符对称, 比如: “aba”。代码里用 index 来代表 i.
public static int maxLengthMiddle(char[] array, int index) { int length = 1; //最长的子字符串长度 int j = 1; //前后移动的指针 while ((array[index - j] == array[index + j]) && (index - j) >= 0 && array.length > (index + j)) { length += 2; j++; } return length; }
2. 第 i 个字符串是对称字符串的其中一个中心。比如“abba”。
public static int maxLengthMirror(char[] array, int index) { int length = 0; //最长的子字符串长度 int j = 0; //前后移动的指针 while ((array[index - j] == array[index + j + 1]) && (index - j) >= 0 && array.length > (index + j + 1)){ length += 2; j++; } return length; }
有了这样两个函数,我们只需要遍历字符串里所有的字符,就可以找出最大长度的对称子字符串了。
public static int palindrain(char[] array) { if (array.length == 0) return 0; int maxLength = 0; for (int i = 0; i < array.length; i++) { int tempMaxLength = - 1; int length1 = maxLengthMiddle(array, i); int length2 = maxLengthMirror(array, i); tempMaxLength = (length1 > length2) ? length1 : length2; if (tempMaxLength > maxLength) { maxLength = tempMaxLength; } } return maxLength; }
因为找出以第 i 个字符为“中心”对称字符串复杂度为 O(N),所以整个算法的复杂度为O(N^2)。
这里有另一种方法算法,复杂度是一样,但是,看起来更简洁一点。
public class Palindrome { public static void main(String[] args) { Palindrome pld = new Palindrome(); System.out.println(pld.longestPalindrome("abcc")); } String getPalindrome(String s, int l, int r) { int n = s.length(); while (l >= 0 && r <= n-1 && s.charAt(l) == s.charAt(r)) { l--; r++; } return s.substring(l + 1, r); } String longestPalindrome(String s) { int n = s.length(); if (n == 0) return ""; String longest = s.substring(0, 1); for (int i = 0; i < n-1; i++) { String p1 = getPalindrome(s, i, i); if (p1.length() > longest.length()) { longest = p1; } String p2 = getPalindrome(s, i, i+1); if (p2.length() > longest.length()) { longest = p2; } } return longest; } }
有一种可以把复杂度降到O(N)的算法,但是这个算法要利用 suffix tree, 有兴趣的可以搜索一下。
参考:http://www.leetcode.com/2011/11/longest-palindromic-substring-part-i.html
转载请注明出处:http://blog.csdn.net/beiyeqingteng