LintCode 10 String Permutation II

思路

与Permutation的思路类似，使用与subsets II相同的去重思路。DFS搜索。
时间复杂度O(n!)
空间复杂度O(n)

代码

public class Solution {
    /*** @param str: A string* @return: all permutations*/public List<String> stringPermutation2(String str) {
    // write your code hereList<String> results = new ArrayList<>();if (str == null) {
    return results;}char[] strArray = str.toCharArray();boolean[] visit = new boolean[str.length()];Arrays.sort(strArray);dfs(strArray, visit, new StringBuilder(), results);return results;}private void dfs(char[] str, boolean[] visit, StringBuilder cur, List<String> results) {
    if (cur.length() == str.length) {
    results.add(cur.toString());return;}for (int i = 0; i < str.length; i++) {
    if (visit[i]) {
    continue;}if (i > 0 && str[i] == str[i - 1] && !visit[i - 1]) {
    continue;}cur.append(str[i]);visit[i] = true;dfs(str, visit, cur, results);cur.deleteCharAt(cur.length() - 1);visit[i] = false;}}
}