今天碰到一个面试题目：求N个字符串中的最大公子串

对的

是的是一种树形结构呵呵..以前写过..

我想问一下
如果 字符串是 acdb,dcba,cabd
那最大公字串是什么呢？

看到你的这个例子，我觉的我的思路里需要将字符串平移，
还有你的例子很好，一个字符串的全排列，可以检验一些思路正不正确

动态规划。

动态规划。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
* 求N个字符串中的最大公子串
* 思路：先找出字符串中最短的那个字符串,然后依次取出最短字符串中的每个字符与其余字符串进行比较。
*/
public class ShortString {
//字符串列表中的最短字符串
public String shortStr(ArrayList<String> strings){
return Collections.min(strings, new Comparator<String>(){
@Override
public int compare(String str1, String str2) {
if(str1.length()<str2.length())
return -1;
else if(str1.length()==str2.length())
return 0;
else if(str1.length()>str2.length())
return 1;
return 0;
}

});
}
//判断字符串列表中的每个字符串是否包含指定字符串，如果有一个不包含就返回false
public boolean contains(ArrayList<String> strings,String str){
for(String s:strings){
if(!s.contains(str))
return false;
}
return true;
}
//最短公共字符串
public String maxSubString(ArrayList<String> strings){
String maxStr ="";//最长的公字符串
String tempStr="";//临时变量
String minStr=shortStr(strings);//所有字符串中的最短字符串
int i = 0;
for( i = 0;i<minStr.length();i++){
tempStr += minStr.charAt(i);
if(contains(strings,tempStr)){
//新公子串长度大于原来公子串，maxStr重新赋值
if(maxStr.length()<tempStr.length())
maxStr = tempStr;
}
else {
//如果剩余的字符数小于公子串长度，就没有必要再比较了
if(minStr.length()-i<maxStr.length())
break;
tempStr = minStr.charAt(i)+"";
}
}
return maxStr;
}

public static void main(String[] args) {
ArrayList<String> strings = new ArrayList<String>(Arrays.asList("ababcghy","abcdeftdsfgsdg","abcdefsdf"));
ShortString ss = new ShortString();
System.out.println("字符串列表："+ strings);
System.out.println("最短字符串："+ss.shortStr(strings));
System.out.println("最长公子串："+ss.maxSubString(strings));

}
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * 求N个字符串中的最大公子串
 * 思路：先找出字符串中最短的那个字符串,然后依次取出最短字符串中的每个字符与其余字符串进行比较。
 */
public class ShortString {
	//字符串列表中的最短字符串
	public String shortStr(ArrayList<String> strings){
		return Collections.min(strings, new Comparator<String>(){
			@Override
			public int compare(String str1, String str2) {
				if(str1.length()<str2.length())
					return -1;
				else if(str1.length()==str2.length())
					return 0;
				else if(str1.length()>str2.length())
					return 1;
				return 0;
			}
			
		});
	}
	//判断字符串列表中的每个字符串是否包含指定字符串，如果有一个不包含就返回false
	public boolean contains(ArrayList<String> strings,String str){
		for(String s:strings){
			if(!s.contains(str))
				return false;
		}
		return true;
	}
	//最短公共字符串
	public String maxSubString(ArrayList<String> strings){
		String maxStr ="";//最长的公字符串
		String tempStr="";//临时变量
		String minStr=shortStr(strings);//所有字符串中的最短字符串
		int i = 0;
		for( i = 0;i<minStr.length();i++){
			tempStr += minStr.charAt(i);
			if(contains(strings,tempStr)){
				//新公子串长度大于原来公子串，maxStr重新赋值
				if(maxStr.length()<tempStr.length())
					maxStr = tempStr;
			}
			else {
				//如果剩余的字符数小于公子串长度，就没有必要再比较了
				if(minStr.length()-i<maxStr.length())
					break;
				tempStr = minStr.charAt(i)+"";
			}
		}
		return maxStr;
	}
	
	public static void main(String[] args) {
		ArrayList<String> strings = new ArrayList<String>(Arrays.asList("ababcghy","abcdeftdsfgsdg","abcdefsdf"));
		ShortString ss = new ShortString();
		System.out.println("字符串列表："+ strings);
		System.out.println("最短字符串："+ss.shortStr(strings));
		System.out.println("最长公子串："+ss.maxSubString(strings));
		
	}
}

操作字符串用 StringBuffer,不用String

是什么？