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

题目

 

     输入一个字符串，输出该字符串中对称的子字符串的最大长度。
     比如输入字符串"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一下吧。。

 

评论

4 楼 fayedShih 2011-09-21  

没有对齐，再发一次。

public class FindSymmetric {
public static void main(String[] args) {
FindSymmetric fs = new FindSymmetric();
String s = "abcabccbaaddsaddaaddaswdfwfwss";
String matched = fs.findMatch(s);
if (matched != null)
System.out.println("Longest symmetric string '" + matched + "'");
}

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;
}
}

3 楼 fayedShih 2011-09-21  

只做了个偶数的对称匹配。

public class FindSymmetric {
public static void main(String[] args) {
FindSymmetric fs = new FindSymmetric();
String s = "abcabccbaaddsaddaaddaswdfwfwss";
String matched = fs.findMatch(s);
if (matched != null)
System.out.println("Longest symmetric string '" + matched + "'");
}

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;
}
}

2 楼 jbm3072 2011-06-08  

Jathon_hs 写道

试试这个

		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"这样的对称字符情况。

1 楼 Jathon_hs 2011-06-08  

试试这个

		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);