题目 https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
解法 使用 DFS
res.toArray(new String[res.size()]) 很耗性能
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution public String[] permutation(String s) { List<String> res = new ArrayList<>(); int len = s.length(); char [] c = s.toCharArray(); dfs(0 , c, res); return res.toArray(new String[res.size()]); } private void dfs (int x, char [] chars, List<String> res) if (chars == null || chars.length == 0 ) return ; if (x == chars.length -1 ) { res.add(String.valueOf(chars)); return ; } Set<Character> set = new HashSet<>(); for (int i=x; i<chars.length; i++) { if (set.contains(chars[i])) continue ; set.add(chars[i]); swap(i, x, chars); dfs(x+1 , chars, res); swap(i, x, chars); } } private void swap (int a, int b, char [] chars) char c = chars[a]; chars[a] = chars[b]; chars[b] = c; } }
