[输入一个字符串，输出该字符串中对称的子字符串的最大长度][答题方法]

[输入一个字符串，输出该字符串中对称的子字符串的最大长度][解题方法]

题目

?

?? ? 输入一个字符串，输出该字符串中对称的子字符串的最大长度。
???? 比如输入字符串"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[i] == string[i + 1]) {int temp = expandSymetry(string, i, i + 1);if(temp>max) {max= temp;}}}//寻找长度为3以上的奇数最大对称串for(int i=0;i<length-2;i++) {if(string[i] == string[i+2]) {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[j+m]!=string[i-m]) {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[i] != string[j]) {return false;}}return true;}}

?

?

?? 你有什么简单的方法吗？Share一下吧。。

?

String str = "abcabccbaaddsaddaaddaswdfwfwss";char[] c = str.toCharArray();int max = 0;for (int i = 0; i < c.length - 1; i++) {if (c[i] == c[i + 1]) {for (int m = i - 1, n = i + 2; m >= 0 && n < c.length; m--, n++) {if (c[m] != c[n]) {int t = n - m - 1;if (t > max) {max = t;}break;}}}}System.out.println(max);String str = "abcabccbaaddsaddaaddaswdfwfwss";char[] c = str.toCharArray();int max = 0;for (int i = 0; i < c.length - 1; i++) {if (c[i] == c[i + 1]) {for (int m = i - 1, n = i + 2; m >= 0 && n < c.length; m--, n++) {if (c[m] != c[n]) {int t = n - m - 1;if (t > max) {max = t;}break;}}}}System.out.println(max);
这个代码MS没有考虑"aba"这样的对称字符情况。}

private String findMatch(String s) {
char[] chars = s.toCharArray();
// System.out.println("start is "+start+" end is "+end);
int max = 0, start = 0, end = 0, i, j;
for (i = 0; i < chars.length; i++)
for (j = chars.length - 1; j > i; j--) {
// System.out.println("chars[j] is " + chars[j]);
if (chars[i] == chars[j]) {
// System.out.println("matched");
if (j - i > max && isSymmetric(chars, i, j)) {
// System.out.println("j is " + j);
max = j - i;
start = i;
end = j;
}
}
}
if (max > 0)
return s.substring(start, end + 1);
System.out.println("Asymmetric string");
return null;
}

private boolean isSymmetric(char[] chars, int i, int j) {
if ((j - i) % 2 == 0)
return false;
for (; i < j; i++, j--)
if (chars[i] != chars[j])
return false;
return true;
}
}}

private String findMatcicih(String s) {
char[] chars = s.toCharArray();
// System.out.println("start is "+start+" end is "+end);
int max = 0, start = 0, end = 0, i, j;
for (i = 0; i < chars.length; i++)
for (j = chars.length - 1; j > i; j--) {
// System.out.println("chars[j] is " + chars[j]);
if (chars[i] == chars[j]) {
// System.out.println("matched");
if (j - i > max && isSymmetric(chars, i, j)) {
// System.out.println("j is " + j);
max = j - i;
start = i;
end = j;
}
}
}
if (max > 0)
return s.substring(start, end + 1);
System.out.println("Asymmetric string");
return null;
}

private boolean isSymmetric(char[] chars, int i, int j) {
if ((j - i) % 2 == 0)
return false;
for (; i < j; i++, j--)
if (chars[i] != chars[j])
return false;
return true;
}
}

查看更多 下一篇