经典面试题20 - 字符串的全排列

问题

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

例如输入字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串
abc、acb、bac、bca、cab 和 cba。

解答

递归实现
从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理，从而得到所有元素的全排列。

以对字符串abc进行全排列为例:
固定a，求后面bc的排列：abc，acb，求好后，a和b交换，得到bac
固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到cba
固定c，求后面ba的排列：cba，cab。

下面是 Swift 语言的编码

class Permutation{
    var count = 0

    func calcAllPermutation(arr: [String], from: Int, to: Int) {
        //Define mutable object since below swap method need mutable type.
        var temp: [String] = arr
        if to <= 1 {
            return
        }

        if from == to {
            count += 1
            print(arr)
        } else {
            for i in from ..< to {
                let result:Bool = isCanSwap(arr: temp, from: from, to: i)
                if result {
                    if i != from {
                        swap(&temp[i], &temp[from])
                    }

                    calcAllPermutation(arr: temp, from: from + 1, to: to)

                    if i != from {
                        swap(&temp[i], &temp[from])
                    }
                }
            }
        }
    }


    func isCanSwap(arr: [String], from: Int, to: Int) -> Bool {
        var result: Bool = true

        for i in from ..< to {
            if arr[i] == arr[to] {
                result = false
                break
            }
        }
        return result
    }
}

更多

经典面试100题 - 持续更新中

获取更多内容请关注微信公众号豆志昂扬:

• 直接添加公众号豆志昂扬；
• 微信扫描下图二维码；