内容简介:假设已经得到了除了当前字符之外的其它字符拼接好的字符串,则与当前字符进行拼接。递归的想法是0..i的字符不变,将i..n-1的字符排列组合进行拼接。动态规划的想法是:将第i个字符换为每个可以替换的字符,可以替换的字符是i+1往后的所有字符。将替换后的结果存储下来,在此基础上的所有字符串替换下一个i+1字符为所有可以替换的字符,即可保证获得所有的排列组合。这个想法更接近排列组合的算法思想。
方法一:递归
假设已经得到了除了当前字符之外的其它字符拼接好的字符串,则与当前字符进行拼接。
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 知识
以上所述就是小编给大家介绍的《无重复字符串的排列组合(golang)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。