题解 | JAVA 递归+回溯 #字符串的排列# [P1]

Permutation大部分都能用递归+回溯解决

先build一个charCount把字符串中每个字母的count记下来
recurse的时候从a-z依次选count>0的字母append到输出字符串。

时间: O(n!)
空间: O(n) 栈高

import java.util.*;

public class Solution {
    ArrayList<String> ans = new ArrayList<>();

    public ArrayList<String> Permutation(String str) {
      int[] charCount = new int[26];
      for (char c : str.toCharArray())
        charCount[c-'a']++;
      
      recurse(charCount, str.length(), new StringBuilder());
      return ans;
    }
  
    public void recurse(int[] charCount, int strlen, StringBuilder sb) {
      if (sb.length() == strlen) {  // basecase
        ans.add(sb.toString());
        return;
      }

      for (int i = 0; i < 26; i++) {
        if (charCount[i] != 0) {
          charCount[i]--;
          sb.append((char)('a'+i));
          recurse(charCount, strlen, sb);
          // 回溯
          sb.deleteCharAt(sb.length()-1);
          charCount[i]++;
        }
      }
    }
}