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

薇清潜 · · 869 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

方法一：递归

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

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
}

有疑问加站长微信联系（非本文作者）