Longest Common SubString, 又称为”LCS”问题


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func lengthOfLongestSubstring(s string) int {

start := 0
end := 0
repeatCount := 0

slen := len(s)

m := make(map[byte]byte)

for end < slen {
tmp := s[end]
if _,ok := m[tmp];!ok {
m[tmp] = tmp
end++
repeatCount = int(math.Max(float64(repeatCount),float64(end-start)))

} else {
delete(m,s[start])
start++

}

}
return repeatCount

}


如图

如图

如图

参考,
所谓容器,即一个map

更多参考:

图解LeetCode第 3 号问题:无重复字符的最长子串

无重复字符的最长子串

最长公共子序列和最长公共子串

动态规划求解最长公共子序列

笔试面试算法经典–最长公共子串(Longest Common SubString)