IOS 算法(中级篇) ----- 无重复字符串的排列组合

今天看一道面试题, 很有趣
题目: 求无重复字符串的排列组合。(字符都是英文字母且长度在[1, 9]之间)

例:
给定: s = "qwe"
返回：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

给定: s = "ab"
返回：["ab", "ba"]

解题思路

这个题目比较好的地方是规定了 字符串每个字符均不相同, 减少了我们很多判断处理
全排列+交换法, 交换位置之后再递归回溯

例如 初始字符串 qwe, 我们定义一个index = 0, 初始数组, [qwe]

第一轮，数组每个元素用index 0以上的，跟0做交换，得到：
wqe, eqw 加上初始qwe, 我们得到这样一个数组 [qwe, wqe, eqw]

第二轮，新数组每个元素用index 1以上的，跟1做交换，得到：
qew, weq, ewq, 加上之前那些 得到 [qwe, wqe, eqw, qew, weq, ewq]

show.png

为了便于理解我们再看个例子 初始字符串 JQKA, index = 0, [JQKA]

第一轮，index 0以上的，跟0做交换，得到：
QJKA, KQJA, AQKJ
数组: [JQKA, QJKA, KQJA, AQKJ]

第二轮，index 1以上的，跟1做交换，得到：
JKQA, JAKQ, QKJA, QAKJ, KJQA, KAJQ, AKQJ, AJKQ

数组: [JQKA, QJKA, KQJA, AQKJ, JKQA, JAKQ, QKJA, QAKJ, KJQA, KAJQ, AKQJ, AJKQ]

第三轮，index 2以上的，跟2做交换，得到：
JQAK QJAK KQAJ
AQJK JKAQ JAQK
QKAJ QAJK KJAQ
KAQJ AKJQ AJQK

数组: [JQKA, QJKA, KQJA, AQKJ, JKQA, JAKQ, QKJA, QAKJ, KJQA, KAJQ, AKQJ, AJKQ, JQAK QJAK KQAJ, AQJK JKAQ JAQK, QKAJ QAJK KJAQ, KAQJ AKJQ AJQK]

完成返回

按着这个思路我们可写算法

    func permutation(_ S: String) -> [String] {
        var index = 0
        var result:[String] = [S]
        while index < S.count {
            for i in 0..<result.count {
                for j in index+1..<result[i].count {
                    let swapStr = swapCharacters(result[i], index, j);
                    result.append(swapStr);
                }
            }
            index+=1;
        }
        return result;
    }
    
    //字符串指定两个位置字符互换位置方法
    func swapCharacters(_ send: String, _ index1:Int, _ index2:Int) -> String     {
        var characters = Array(send)
        characters.swapAt(index1, index2)
        return String(characters)
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址