数据结构(1): 字符串

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 最长回文子串

LeetCode No.5

问题：找出一个子串包含的最长回文子串。
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
}