面试题 08.07. 无重复字符串的排列组合：

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

样例 1：

 输入：
 	S = "qwe"
 	
 输出：
 	["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

样例 2：

 输入：
 	S = "ab"
 	
 输出：
 	["ab", "ba"]

提示：

字符都是英文字母。
字符串长度在[1, 9]之间。

分析

面对这道算法题目，二当家的陷入了沉思。
题目说 字符串每个字符均不相同，那我们全排列就可以考虑成字符所在位置或者说是数组的下标的不同排列，因为字符都不同，所以我们就不必关心每个字符是什么了。
可以开辟空间存储中间排列，这样我们需要能判断某个字符是否被选择过，可以用hash表存储当前排列结果，然后去看是否含有当前字符。
也可以直接用交换的方式模拟排列，每个字符在所有位置上都排一次不就是全排列吗？先轮着放第一个位置，然后轮着放第二个位置，以此类推。

题解

rust

impl Solution {
    pub fn permutation(mut s: String) -> Vec<String> {
        fn dfs(s: &mut Vec<u8>, pos: usize, ans: &mut Vec<String>) {
            if pos == s.len() {
                ans.push(String::from_utf8(s.clone()).unwrap());
                return;
            }
            // 当前位置保持不变，接着排下一个
            dfs(s, pos + 1, ans);
            // 换后面的某一个到当前位置
            (pos + 1..s.len()).for_each(|i| {
                s.swap(pos, i);
                dfs(s, pos + 1, ans);
                s.swap(pos, i);
            });
        }

        let mut ans = Vec::new();
        dfs(&mut s.into_bytes(), 0, &mut ans);

        ans
    }
}

go

func permutation(S string) []string {
    s := []byte(S)
	n := len(S)
	var ans []string

	var dfs func(int)
	dfs = func(pos int) {
		if pos == n {
			ans = append(ans, string(s))
			return
		}
		// 当前位置保持不变，接着排下一个
		dfs(pos + 1)
		// 换后面的某一个到当前位置
		for i := pos + 1; i < n; i++ {
			s[pos], s[i] = s[i], s[pos]
			dfs(pos + 1)
			s[pos], s[i] = s[i], s[pos]
		}
	}

	dfs(0)

	return ans
}

typescript

function permutation(S: string): string[] {
    const dfs = (pos: number) => {
        const swap = (a: number, b: number) => {
            const t = s[a];
            s[a] = s[b];
            s[b] = t;
        };

        if (pos == s.length) {
            ans.push(s.join(''));
            return
        }
           
        // 当前位置保持不变，接着排下一个
        dfs(pos + 1)
        // 换后面的某一个到当前位置
        for (let i = pos + 1; i < s.length; i++) {
            swap(pos, i);
            dfs(pos + 1)
            swap(pos, i);
        }
    };

    let s = S.split('');
    let ans = [];
    dfs(0);
    return ans;
};

c

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
char** permutation(char* S, int* returnSize){
    int l = strlen(S);
    *returnSize = l;
    for (int i = 2; i < l; ++i) {
        *returnSize *= i;
    }

    char **ans = (char **) malloc(*returnSize * sizeof(char *));

    int ansSize = 0;

    dfs(S, l, 0, ans, &ansSize);

    return ans;
}

void dfs(char* S, int l, int pos, char **ans, int *ansSize) {
    if (pos == l) {
        ans[*ansSize] = (char *) malloc((l + 1) * sizeof(char));
        strcpy(ans[*ansSize], S);
        ++*ansSize;
        return;
    }
    // 当前位置保持不变，接着排下一个
    dfs(S, l, pos + 1, ans, ansSize);
    // 换后面的某一个到当前位置
    for (int i = pos + 1; i < l; ++i) {
        swap(S, pos, i);
        dfs(S, l, pos + 1, ans, ansSize);
        swap(S, pos, i);
    }
}

void swap(char* S, int a, int b) {
    S[a] ^= S[b];
    S[b] ^= S[a];
    S[a] ^= S[b];
}

c++

class Solution {
private:
    void dfs(string &S, int pos, vector<string> &ans) {
        if (pos == S.size()) {
            ans.emplace_back(S);
            return;
        }
        // 当前位置保持不变，接着排下一个
        dfs(S, pos + 1, ans);
        // 换后面的某一个到当前位置
        for (int i = pos + 1; i < S.size(); ++i) {
            swap(S[pos], S[i]);
            dfs(S, pos + 1, ans);
            swap(S[pos], S[i]);
        }
    }
public:
    vector<string> permutation(string S) {
        vector<string> ans;
        dfs(S, 0, ans);
        return ans;
    }
};

java

class Solution {
    public String[] permutation(String S) {
		List<String> ans = new ArrayList<>();
		dfs(S.toCharArray(), 0, ans);

		return ans.toArray(new String[ans.size()]);
	}

	private void dfs(char cs[], int pos, List<String> ans) {
		if (pos == cs.length) {
			ans.add(new String(cs));
			return;
		}

        dfs(cs, pos + 1, ans);

		for (int i = pos + 1; i < cs.length; ++i) {
			swap(cs, pos, i);
			dfs(cs, pos + 1, ans);
			swap(cs, pos, i);
		}
	}

	private void swap(char[] cs, int a, int b) {
		cs[a] ^= cs[b];
		cs[b] ^= cs[a];
		cs[a] ^= cs[b];
	}
}

python

class Solution:
    def permutation(self, S: str) -> List[str]:
        S = list(S)
        n = len(S)
        ans = []
        def dfs(pos: int) -> None:
            if pos == n:
                ans.append("".join(S))
                return
            # 当前位置保持不变，接着排下一个
            dfs(pos + 1)
            # 换后面的某一个到当前位置
            for i in range(pos + 1, n):
                S[pos], S[i] = S[i], S[pos]
                dfs(pos + 1)
                S[pos], S[i] = S[i], S[pos]
        dfs(0)
        return ans