public class MaxCatenate {
/*
* Q.37 有n 个长为m+1 的字符串,如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配,则两个字符串可以联接,
* 问这n 个字符串最多可以连成一个多长的字符串,如果出现循环,则返回错误。
*/
public static void main(String[] args){
String[] text = new String[]{
"abcd",
"bcde",
"cdea",
"deab",
"eaba",
"abab",
//"babc",
"deac",
"cdei",
"bcdf",
"cdfi",
"dfic",
"cdfk",
"bcdg",
};
new MaxCatenate().maxCatenate(text);
}
public void maxCatenate(String[] text){
int size=text.length;
int[][] adjMatrix=new int[size][size];
//create Graph.Use adjacent matrix
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
if(this.hasEdge(text[i],text[j])){
adjMatrix[i][j]=1;
}
}
}
//create a new array to keep the 'adjMatrix'unchanged.
int[][] finalCost=new int[size][size];
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
finalCost[i][j]=adjMatrix[i][j];
}
}
int max=0;
for(int k=0;k<size;k++){
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
if(finalCost[i][k]!=0&&finalCost[k][j]!=0&&
finalCost[i][k]+finalCost[k][j]>finalCost[i][j] ){
finalCost[i][j]=finalCost[i][k]+finalCost[k][j];
max=(max>finalCost[i][j]?max:finalCost[i][j]);
}
}
}
}
for(int i=0;i<size;i++){
if(finalCost[i][i]>1){//not '>0',consider "bbbb"
System.out.println("circle detected");
return;
}
}
System.out.println("maxLength is "+(max+1));
}
//true if strA's last m characters equals to strB's first m characters
public boolean hasEdge(String strA,String strB){
boolean result=false;
String suffix=strA.substring(1);
result=strB.startsWith(suffix);
return result;
}
}
分享到:
相关推荐
29.java字符串+操作.zip29.java字符串+操作.zip29.java字符串+操作.zip29.java字符串+操作.zip29.java字符串+操作.zip29.java字符串+操作.zip29.java字符串+操作.zip29.java字符串+操作.zip29.java字符串+操作.zip29...
不需要关心接受的字符串编码是UTF_8还是GBK,还是ios-8859-1,自动转换为utf-8编码格式,无需判断字符串原有编码,用法://处理编码String newStr = GetEncode.transcode(oldStr);
字符串逆序+c语言字符串逆序输出+c语言字符串逆序逐行解释字符串逆序+c语言字符串逆序输出+c语言字符串逆序逐行解释字符串逆序+c语言字符串逆序输出+c语言字符串逆序逐行解释字符串逆序+c语言字符串逆序输出+c语言...
java.util.Date与java.sql.Date互转及字符串转换为日期时间格式.docx
请编写函数fun,,函数的功能是:将放在字符串数组中的M个字符串(每串的长度不超过N),按顺序合并组成一个新的字符串。函数fun中给出的语句仅供参考。 例如,字符串数组中的M个字符串为 AAAA BBBBBBB CC 则合并后...
java 字符串转16进制 16进制转字符串 将两个ASCII字符合成一个字节; java 字符串转16进制 16进制转字符串 将两个ASCII字符合成一个字节; java 字符串转16进制 16进制转字符串 将两个ASCII字符合成一个字节; java ...
在producer端输入字符串并回车,查看consumer端是否显示。 分布式连通性测试 配置修改 bin/kafka-topics.sh --zookeeper localhost:2181 --alter --topic my-topic --config max.message.bytes=128000 bin/...
JAVA的字符串拼接与性能 概述:本文主要研究的是JAVA的字符串拼接的性能,原文中的测试代码在功能上并不等价,导致concat的测试意义不大。不过原作者在评论栏给了新的concat结果,如果有兴趣的同学建议自己修改代码...
89.java字符串方法.zip89.java字符串方法.zip89.java字符串方法.zip89.java字符串方法.zip89.java字符串方法.zip89.java字符串方法.zip89.java字符串方法.zip89.java字符串方法.zip89.java字符串方法.zip89.java字符...
字符串类型是Redis中最为基础的数据存储类型 它在Redis中是二进制安全的 这便意味着该类型可以接受任何格式的数据 如JPEG图像数据或Json对象描述信息等 在Redis中字符串类型的Value最多可以容纳的数据长度是512M ...
字符串循环左移 4/88 给定一个字符串S[0…N-1],要求把S的前k 个字符移动到S的尾部,如把字符串"abcdef" 前面的2个字符'a'、'b'移动到字符串的尾 部,得到新字符串"cdefab":即字符串循环 左移k。 多说一句:循环...
95.java拼接字符串案例.zip95.java拼接字符串案例.zip95.java拼接字符串案例.zip95.java拼接字符串案例.zip95.java拼接字符串案例.zip95.java拼接字符串案例.zip95.java拼接字符串案例.zip95.java拼接字符串案例.zip...
* 正则统计字符串出现次数 * * @param source * @param regexNew * @return int */ public static int finder(String source, String regexNew) { String regex = "[a-zA-Z]+"; if (regexNew != ...
96.java字符串反转案例.zip96.java字符串反转案例.zip96.java字符串反转案例.zip96.java字符串反转案例.zip96.java字符串反转案例.zip96.java字符串反转案例.zip96.java字符串反转案例.zip96.java字符串反转案例.zip...
如果要检索的字符串值没有出现,则该方法返回 -1。 方法二:match() var str = "123" var reg = RegExp(/3/); if(str.match(reg)){ //包含; } match() 方法可在字符串内检索指定的值,或找到一个或多个正则表达式...
CC++全排列..1--n的全排列以及字符串的全排列
fastjson-1.2.83.jar下载,fastjson是阿里巴巴的开源JSON解析库,可以解析JSON格式的字符串,支持将Java Bean序列化为JSON字符串,也支持从JSON字符串反序列化到JavaBean。fastjson采用全新的JSON解析算法,运行速度极快...
如果第一个参数为负值,则表示从字符串的尾部开始计算下标位置,即 -1 表示 最后一个字符,-2 表示倒数第二个字符,以此类推。这对于左侧字符长度不固 定时非常有用。 ECMAScript 不再建议使用该方法,推荐使
编写程序完成如下功能:输出字符串“www.google.com”的长度,并分别计算并显示出‘o’ 与‘g’的个数,截取其中“google”进行输出显示。 2、编写程序,尝试用“==”与equals()方法比较“Hello java”与“Hello ...
用字符串常量为字符指针初始化,其形式与字符数组的初始化类似,却有本质上的区别:字符数组获得字符串所有的字符,而字符指针获得字符串首地址,与字符串内的字符无关。 【例8.4】用指向字符串的指针变量完成两个...