1.1 字符串移位
问题：将字符的前k个字符移到字符串结尾。 Input：“abcde”，2 Output：“cdeab”
三步翻转法： 将字符串分为前k位和后（n-k）位两部分，将两部分分别翻转，最后再整体翻转即可。 时间复杂度：T = O(n) 参考原文
示例代码：
// 反转字符串
func reverse(s string) string {
runes := []rune(s)
for l, r := 0, len(runes) - 1; l < r; l, r = l + 1, r - 1 {
runes[l], runes[r] = runes[r], runes[l]
}
return string(runes)
}
// 三步反转法对字符串进行循环移位
func shift_string(s string, k int) string {
runes := []rune(s)
ls, rs := runes[:k], runes[k:]
rls := reverse(string(ls))
rrs := reverse(string(rs))
return reverse(rls + rrs)
}
1.2 最长回文子串
问题：找出一个子串包含的最长回文子串。 Input: s = “babad” Output: “bab” Note: “aba” is also a valid answer.
解法1：从某个子串向两边扩展，遍历找出最长的一个（需要考虑偶数个、奇数个字符的回文子串）
示例代码
func LongestPalindrome(s string) string {
rs := []rune(s)
mx, st := 0, 0
i, j, c := 0, 0, 0
for i = 0; i < len(rs); i++ {
// 奇数个字符的回文子串
for j = 0; i - j >= 0 && i + j < len(rs); j++ {
if rs[i - j] != rs[i + j] {
break
}
c = 2 * j + 1
}
if c > mx {
mx = c
st = i - j + 1
}
// 偶数个字符的回文子串
for j = 0; (i - j) >= 0 && (i + j + 1) < len(rs); j++ {
if rs[i - j] != rs[i + j + 1] {
break
}
c = j * 2 + 2
}
if c > mx {
mx = c
st = i - j + 1
}
}
return string(rs[st: st + mx])
}
解法2：马拉车算法 具体思路参考原文
示例代码：
func min(x, y int) int {
if x < y {
return x
}
return y
}
func LongestPalindrome1(s string) string {
if len(s) < 2 {
return s
}
news := make([]rune, len(s))
news[0] = '#'
for _, r := range s {
news = append(news, r)
news = append(news, '#')
}
dp := make([]int, len(news))
mx, center, maxlen, maxst := 0, 0, 1, 0
for i := 0; i < len(news); i++ {
// 算法核心转移方程
if i < mx {
dp[i] = min(mx - i, dp[2*center - i])
}
// 以i为中心，只接从距离i为d[i] + 1的位置扩散
left, right := i - (1 + dp[i]), i + (1+ dp[i])
for left >= 0 && right < len(news) && news[left] == news[right] {
dp[i]++
left++
right--
}
// 更新mx
if i + dp[i] > mx {
mx = i + dp[i]
center = i
}
// 更新最大长度和对应在源字符串的起始位置
if dp[i] > maxlen {
maxlen = dp[i]
maxst = (i - maxlen) / 2
}
}
return s[maxst : maxst + maxlen]
}
1.3 字符串的全排列
问题描述：输入一个字符串，打印出该字符串中字符的所有排列。 例如输入字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。
解法1：递归方法DFS搜索，想象成树
示例代码:
var res = []string{}
func dfs_search(s string, lv int, cur string) {
if lv == 0 {
res = append(res, cur)
}
for i := 0; i < len(s); i++ {
// 去掉当前字符，下一层在剩下的字符中挑
dfs_search(s[:i] + s[i+1:], lv - 1, cur + string(s[i]))
}
}
func FullPermutation(s string) []string {
res = []string{}
dfs_search(s, len(s), "")
return res
}
解法2：字典序排列，从当前字符串s生成刚好比他大的下一个字符串排列 参考原文
- 找到排列中最后一个升序的位置i
- 找到i后面最后一个比s[i]大的位置j
- 交换s[i]和s[j]
- 将i+1之后的字符串反转
示例代码:
// 字典序排列算法
func next_permutation(s string) (bool, string) {
rs := []rune(s)
i, j := 0, 0
// 找到最后一个升序的位置i
for i = len(rs) - 2; i >= 0 && rs[i] >= rs[i+1]; i-- {}
if i < 0 {
return false, ""
}
// 找到i后面最后一个比rs[i]大的位置j
for j = len(rs) - 1; j > i && rs[j] <= rs[i]; j-- {}
// 交换rs[i], s[j]
rs[i], rs[j] = rs[j], rs[i]
// 反转rs[i+1:]
rev := reverse(string(rs[i + 1:]))
return true, string(rs[:i+1]) + rev
}
func DictOrderFullPermutation(s string) []string {
res := []string{}
for ok, next_str := true, s; ok; ok, next_str = next_permutation(next_str) {
res = append(res, next_str)
}
return res
}