题解 | #字符串的排列#

// @耗时 14000+
// Tips：并不是很好的代码，希望获得同行指点
import java.util.ArrayList;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        
      	// 结果集
        ArrayList<String> res = new ArrayList<>();
      
      	// 状态数组
        int[] used = new int[10010];
      
      	// 记录每一条路径
      
        StringBuilder path = new StringBuilder();
      
      	// 如果只有字符串的大小只有1或者为空，则直接将字符串加入路径返回
        if(str.length() < 2) {
            res.add(str);
            return res;
        }
      
      	//初始化状态数组
        for (int i = 0; i < str.length(); i++) {
            used[i] = 0;
        }
      
		// dfs递归打印路径
        dfs(res, used, path, str);
      
		// 返回结果
        return res;
    }
    
  	// @param res - 结果集
  	//        used - 状态数组
  	//        path - 路径
  	//        str - 需要全排列的字符串
    public static void dfs(ArrayList<String> res, int[] used, StringBuilder path, String str) {
      
         // 将路径去重，避免入aa -> aa aa 诸如此类的问题
         if (path.length() == str.length()) {
            for (String s:
                 res) {
                if(s.equals(path.toString())){
                    return;
                }
            }
           
            // 添加路径
            res.add(path.toString());
           
            // 返回结果
            return;
        }

        // 遍历字符串中的每一个字符
        for (int i = 0; i < str.length(); i++) {
            // 如果已经被选择了就continue，寻找下一个
            if (used[i] == 1) {
                continue;
            }
          
            // 记录状态 1 - 已使用
          	//		   0 - 未使用
            used[i] = 1;
          
            // 将该值加入路径
            path.append(str.charAt(i));
          
          	// 递归调用
            dfs(res, used, path, str);
          
          	// 底层递归结束后，需要清除之前添加的值，还原路径
            path.deleteCharAt(path.length() - 1);
          
          	// 还原状态数组
            used[i] = 0;
        }


    }
}