-
Notifications
You must be signed in to change notification settings - Fork 0
/
Longest-Substring-Without-Repeating-Characters.go
95 lines (81 loc) · 1.71 KB
/
Longest-Substring-Without-Repeating-Characters.go
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package longestSubstringwithoutrepeatingcharacters
// LengthOfLongestSubstring 暴力解
func LengthOfLongestSubstring(s string) int {
slength := len(s)
if slength == 0 || slength == 1 {
return slength
}
tmpLen := 1
var maxLen = 1
for i := 1; i < slength; i++ {
// 往前找前幾個視窗
j := i - tmpLen
for ; j < i; j++ {
if s[j] == s[i] { // 如果相同,那麼和S[J]到S[I-1]中間的肯定不相同,所以可以直接計算得到
tmpLen = i - j
break
}
}
if j == i { // 都不相同
tmpLen++
}
if tmpLen > maxLen {
maxLen = tmpLen
}
}
return maxLen
}
// LengthOfLongestSubstringMap 用map 紀錄是否重複.
// O(n)
func LengthOfLongestSubstringMap(s string) int {
slength := len(s)
if slength == 0 || slength == 1 {
return slength
}
charMap := make(map[byte]bool)
maxLen, left, right := 0, 0, 0
for left < slength {
if ok := charMap[s[right]]; ok {
// 有找到
charMap[s[left]] = false
left++
} else {
charMap[s[right]] = true
right++
}
if maxLen < right-left {
maxLen = right - left
}
if (left+maxLen) >= slength || right >= len(s) {
break
}
}
return maxLen
}
// LengthOfLongestSubstringBit 用map效能不好時可使用數組改善
func LengthOfLongestSubstringBit(s string) int {
slength := len(s)
if slength == 0 || slength == 1 {
return slength
}
// ASCII 0~255
charMap := [256]bool{}
maxLen, left, right := 0, 0, 0
for left < slength {
if ok := charMap[s[right]]; ok {
// 有找到
charMap[s[left]] = false
left++
} else {
charMap[s[right]] = true
right++
}
if maxLen < right-left {
maxLen = right - left
}
if left+maxLen >= slength || right >= len(s) {
break
}
}
return maxLen
}