golang刷leetcode 技巧（46）有重复字符串的排列组合

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]

示例2:

 输入：S = "ab"
 输出：["ab", "ba"]

提示:

1. 字符都是英文字母。

2. 字符串长度在[1, 9]之间。

解题思路

1，这种问题，一般都是递归解决

2，由于存在重复元素，需要有去重逻辑

3，依次遍历取出每个元素，将它和剩余元素返回结果拼接。

4，对于S中的每个元素i，我们需要判断S［：i] 中是否出现过，如果出现过，我们可以跳过

例子：

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]

1，第一次我们取出第一个q，然后和 “qe”的结果拼接

2，第二次我们取第二个q的时候，和第一次计算结果一致，因此可以不必计算

代码实现

func permutation(S string) []string {
    var r []string
    if len(S)==0{
        r=append(r,"")
        return r
    }
    for i:=0;i<len(S);i++{
        sl:=[]byte(S)
        if !inArray(sl[:i],S[i]){
            var r0 []string
            if i==0{
                r0=permutation(S[1:])
            }else if i==len(S)-1{
                r0=permutation(S[:len(S)-1])
            }else{
                r0=permutation(S[:i]+S[i+1:])
            }
            fmt.Println(r0,string([]byte{S[i]}))
            for j,_:=range r0{
                s:=string([]byte{S[i]})+r0[j]
                r=append(r,s)
            }
        }
    }
    return r
}


func inArray(s []byte ,ta byte)bool{
    for i,_:=range s{
        if s[i]==ta{
            return true
        }
    }
    return false
}