剑指 Offer 38. 字符串的排列

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = “abc”
输出：[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]

限制：

1 <= s 的长度 <= 8

解法一：下一个排列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


func permutation(s string) []string {
    chs := []byte(s)
    n := len(chs)
    sort.Slice(chs, func(i, j int) bool {
        return chs[i] < chs[j]
    })

    ans := append([]string(nil), string(chs))
    nextPermutation := func() bool {
        i := n - 2
        for i >= 0 && chs[i] >= chs[i+1] {
            i--
        }
        if -1 == i {
            return false
        }
        j := n - 1
        for j > i && chs[i] >= chs[j] {
            j--
        }
        chs[i], chs[j] = chs[j], chs[i]
        for l, r := i+1, n-1; l < r; l++ {
            chs[l], chs[r] = chs[r], chs[l]
            r--
        }
        ans = append(ans, string(chs))
        return true
    }
    for nextPermutation() {
    }
    return ans
}

官方题解如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


func reverse(a []byte) {
    for i, n := 0, len(a); i < n/2; i++ {
        a[i], a[n-1-i] = a[n-1-i], a[i]
    }
}

func nextPermutation(nums []byte) bool {
    n := len(nums)
    i := n - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }
    if i < 0 {
        return false
    }
    j := n - 1
    for j >= 0 && nums[i] >= nums[j] {
        j--
    }
    nums[i], nums[j] = nums[j], nums[i]
    reverse(nums[i+1:])
    return true
}

func permutation(s string) (ans []string) {
    t := []byte(s)
    sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
    for {
        ans = append(ans, string(t))
        if !nextPermutation(t) {
            break
        }
    }
    return
}