乐趣区

关于golang:LeetCode-字符串的排列全排列问题剑指offer38

func permutation(s string) []string {// 思路:应用寻找下一个增长序列 ( 同官网解题)
    // 步骤:1. 升序排序 2. 顺次应用寻找下一个序列查找下一个符合条件的序列 3. 返回后果
    bs := []rune(s)
    l := len(bs)
    if l == 0 || l > 8 {//panic("参数长度异样")
        return []string{}
    }

    sort.Slice(bs, func (a, b int) bool {return bs[a] < bs[b]
    })

    list := make([]string, 0, l)
    for {list = append(list, string(bs))
        if !nextPermutation(bs) {break}
    }
    return list
}

func nextPermutation(bs []rune) bool {l := len(bs)
    // 右边起始查找位,依照之前置换准则,只有右数比左数大能力有下一个更大序列
    lIdx := l - 2
    for lIdx >= 0 && bs[lIdx] >= bs[lIdx+1] {lIdx--}
    if (lIdx < 0) {return false}
    // 从最左边开始找,第一个比 lIdx 大的数即为,最小的大值
    rIdx := l - 1
    for rIdx >= 0 && bs[lIdx] >= bs[rIdx] {rIdx--}
    bs[lIdx], bs[rIdx] = bs[rIdx], bs[lIdx]
    // 依照后面的置换准则,将前面的序列,反转即为新的升序 [)
    reverse(bs[lIdx+1:])
    return true
}

func reverse(list []rune) {for i, l := 0, len(list); i < l/2; i++ {list[i], list[l-1-i] = list[l-1-i], list[i]
    }
}
退出移动版