题解 | #最长公共子串Go#

最长公共子串

http://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac

package main

/**
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
*/
func LCS( s1 string ,  s2 string ) string {
	lenLCCS,indexOfLCCSs1,indexOfLCCSs2 := 0,0,0
	m,n := len(s1),len(s2)
	dp := make([][]int,m+1)
	for i := 0 ; i <= m ; i++ {
		dp[i] = make([]int,n+1)
	}
	for i := 1 ; i <= m ; i++ {
		for j := 1 ; j <= n ; j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
				if dp[i][j] > lenLCCS {
					lenLCCS = dp[i][j]
					indexOfLCCSs1 = i
					indexOfLCCSs2 = j
				}
			}
		}
	}
	var res string
	for i,j := indexOfLCCSs1,indexOfLCCSs2 ; dp[i][j] > 0 ; i,j = i-1,j-1{
		res = string(s1[i-1]) + res
	}
	return res
}
全部评论

相关推荐

牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
湫湫湫不会java:1.在校经历全删了2.。这些荣誉其实也没啥用只能说,要的是好的开发者不是好好学生3.项目五六点就行了,一个亮点一俩行,xxx技术解决,xxx问题带来xxx提升。第一页学历不行,然后啥有价值的信息也没有,到第二页看到项目了,第一个项目九点,第二个项目像凑数的俩点。总体给人又臭又长,一起加油吧兄弟
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务