[输入一个字符串，输出该字符串中对称的子字符串的最大长度][解题方法]
题目输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串"google"，由于该字符串里最长的对称子字符串是"goog"，因此输出4。
思想
首先想到的是采用穷举的方法来分析该问题. 即从最大的对称串开始判断,如果不是，减小一，再找存在不存在对应长度的字符串，依次直到找到对称串长度，返回。
上述方法有点像暴力破解。且没有利用以前的结果。
先设置最大对称串长度max为1，然后找长度是2或者3的对称串，然后对其扩展，直到找到最大对称串，如果最大比max大，将值赋给max。
代码
public class FindMaxSymmetryString { public static void main(String[] args) {char[] string = "abcabccbaa".toCharArray();System.out.println(findMaxSymmetryString2(string));}/** * 方法2 * @param string * @return */public static int findMaxSymmetryString2(char[] string) {int length = string.length;int max = 1;// 寻找长度为2的偶数最大对称串for (int i = 0; i < length - 1; i++) {if (string == string) {int temp = expandSymetry(string, i, i + 1);if(temp>max) {max= temp;}}}//寻找长度为3以上的奇数最大对称串for(int i=0;i<length-2;i++) {if(string == string) {int temp = expandSymetry(string, i, i+2);if(temp>max) {max= temp;}}}return max ;}private static int expandSymetry(char[] string, int i, int j) {int max = j-i+1;int length = string.length;int m = 1;for(; j+m<length && i-m>=0;m++) {if(string!=string) {break;}}return max+2*(m-1);}/** * 方法1 * 从最大对称串开始进行匹配，直到找到最大匹配串 * @param string * @return */public static int findMaxSymmetryString(char[] string) {int length = string.length;for (int i = length; i >= 2; i--) {for (int j = 0; j + i - 1 < length; j++) {if (isSymmetry(string, j, j + i - 1)) {return i;}}}return 1;}private static boolean isSymmetry(char[] string, int start, int end) {for (int i = start, j = end; i < j; i++, j--) {if (string != string) {return false;}}return true;}}
你有什么简单的方法吗？Share一下吧。。
页:
[1]