31

无重复字符串的排列组合（golang）

 3 years ago
source link: https://studygolang.com/articles/29674
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

方法一：递归

假设已经得到了除了当前字符之外的其它字符拼接好的字符串，则与当前字符进行拼接。

func permutation(S string) []string {
    if len(S) == 1 {
        return []string{S}
    }
    // 与拼接得到的各个字符串再进行拼接
    ret := []string{}
    for i, s := range S {
        // 差了第i个字符的剩余字符串往下传，并将得到的结果进行合并
        tmp := fmt.Sprintf("%s%s", S[:i], S[i+1:])
        res := permutation(tmp)
        for _, r := range res {
            ret = append(ret, fmt.Sprintf("%c%s", s, r))
        }
    }
    return ret
}

方法二：动态规划

递归的想法是0..i的字符不变，将i..n-1的字符排列组合进行拼接。动态规划的想法是：将第i个字符换为每个可以替换的字符，可以替换的字符是i+1往后的所有字符。将替换后的结果存储下来，在此基础上的所有字符串替换下一个i+1字符为所有可以替换的字符，即可保证获得所有的排列组合。这个想法更接近排列组合的算法思想。

func permutation(S string) []string {
    if len(S) == 1 {
        return []string{S}
    }
    // 在交换完第i个的所有字符串的基础上进行下一次交换
    list := []string{S}
    l := len(S)
    for i := 0; i < l-1; i ++ {
        for _, item := range list {
            for j := i + 1; j < l; j ++ {
                s := []byte(item)
                s[i], s[j] = s[j], s[i]
                list = append(list, fmt.Sprintf("%s", s))
            }
        }
    }
    return list
}

欢迎关注我们的微信公众号，每天学习Go知识

FveQFjN.jpg!web

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK