本帖最后由 xuhao3622603 于 2015-6-25 13:15 编辑
/*
给定两个字符串,找出其中相同的最长子串。
毕老师在视频中讲的很清楚,但我对代码做了小修改,跟思更加匹配。我在下面会有具体分析。
*/
class StringTest
{
public static void main(String[] args)
{
String s1 = "asdf";
String s2 = "zxsl";
System.out.println(getLong(s1,s2));
}
public static String getLong(String s1,String s2)
{
String max = (s1.length()>=s2.length())?s1:s2;
String min = (max==s1)?s2:s1;
//下面注释掉的是毕老师的原代码
/* for(int x=0;x<min.length();x++)
{
for(int y=0,z=min.length()-x;z<min.length()+1;y++,z++)
{
String temp = min.substring(y,z);
if(max.contains(temp))
return temp;
else
continue;
}
} */
//这是我修改后的代码
for(int x=min.length();x>0;x--)
{
for(int y=0,z=x;z<min.length()+1;y++,z++)
{
String temp = min.substring(y,z);
if(max.contains(temp))
return temp;
else
continue;
}
}
return null;
}
}
两个字符串,取最长子串,毕老师已经经给出具体思路,我的代码还是毕老师的思路,但相比于原代码,我觉得更贴合一点。
先说思路:假设有一把尺子,尺子的长度最开始取短的字符串的长度,然后递减。每一次按照尺子的长度,尺子的头和尾分别是子串的头和尾。从第一个字符开始每次向后顺移一位,保证尺子的末尾不能超出字符串长度。这样第一次尺子的长度跟字符串的长度一样,就把字符串区了出来,与长的字符串进行比较,第二次是取短了一位的尺子,那么能拿出两个子串,以此类推,最后取出长度为一的子串来比较,然后结束。
毕老师先定义了尺子与字符串之间的的长度差,然后字符串长度减去前面的长度差得到尺子的长度,然后长度差逐渐递增造成尺子长度逐渐递减,这是为了能取x=0,x++;方便初学者观看,但思路上并不直观。
我在第一遍看视频的时候,也就是按着毕老师写的来敲得,但第二遍看视频觉得这样不好,就修改了一下代码。直接让尺子的长度x,然后让它递减。下面下面取尺子右面的角标,只需要左角标加上尺子的长度 y+z,而左角标y是0,所以z=x=min.length().相比于要减一下,这个应该更好理解。
|
|