-
Notifications
You must be signed in to change notification settings - Fork 0
/
214.go
77 lines (67 loc) · 1.29 KB
/
214.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
package p214
import (
"bytes"
)
/**
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa", return "aaacecaaa".
Given "abcd", return "dcbabcd".
*/
// todo use kmp
func shortestPalindrome(s string) string {
ss := []byte(s)
length := len(ss)
if length <= 1 {
return s
}
ls, rs := 0, 0
minls, minrs := 0, 0
minPadding := length + 1
for rs < length/2 {
l, r := ls, rs
for {
if l < 0 || r >= length {
if l < 0 && length-r < minPadding {
minls, minrs = ls, rs
minPadding = length - r
} else if r >= length && l+1 < minPadding {
minls, minrs = ls, rs
minPadding = l + 1
}
break
}
if ss[l] == ss[r] {
l--
r++
} else {
break
}
}
if rs == ls {
rs++
} else {
ls++
}
}
var buf bytes.Buffer
if (minls - 0 + 1) == (length - minrs) {
buf.WriteString(s)
} else if (minls - 0 + 1) > (length - minrs) {
buf.WriteString(s)
itx := minls - (length - minrs)
for itx >= 0 {
buf.WriteByte(ss[itx])
itx--
}
} else {
itx := length - 1
end := minrs + minls
for itx > end {
buf.WriteByte(ss[itx])
itx--
}
buf.WriteString(s)
}
return buf.String()
}