題目: 求無重復字符串的排列組合。(字符都是英文字母且長度在[1, 9]之間)

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

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

解題思路

這個題目比較好的地方是規(guī)定了 字符串每個字符均不相同, 減少了我們很多判斷處理
全排列+交換法, 交換位置之后再遞歸回溯

例如 初始字符串 qwe, 我們定義一個index = 0, 初始數(shù)組, [qwe]

第一輪，數(shù)組每個元素用index 0以上的，跟0做交換，得到：
wqe, eqw 加上初始qwe, 我們得到這樣一個數(shù)組 [qwe, wqe, eqw]

第二輪，新數(shù)組每個元素用index 1以上的，跟1做交換，得到：
qew, weq, ewq, 加上之前那些 得到 [qwe, wqe, eqw, qew, weq, ewq]

show.png

為了便于理解我們再看個例子 初始字符串 JQKA, index = 0, [JQKA]

第一輪，index 0以上的，跟0做交換，得到：
QJKA, KQJA, AQKJ
數(shù)組: [JQKA, QJKA, KQJA, AQKJ]

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

數(shù)組: [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

數(shù)組: [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 算法合集地址