Given a string, find all permutations of it without duplicates. Example Given “abb”, return [“abb”, “bab”, “bba”].
Given “aabb”, return [“aabb”, “abab”, “baba”, “bbaa”, “abba”, “baab”].
We can see the keywords in the description of the question is that “find all permutations”. It is easy for us to think that we can use dfs to solve this problem.
publicclass{ * @param str a string * @return all permutations */ public List<String> stringPermutation2(String str){ // Write your code here char[] string = str.toCharArray(); boolean[] isUsed = newboolean[string.length]; Arrays.sort(string); List<String> result = new ArrayList<String>(); String temp = new String(); stringPermutation2Helper(result, temp, string, isUsed); return result; } privatevoidstringPermutation2Helper(List<String> result, String temp, char[] string, boolean[] isUsed){ if (temp.length() == string.length) { result.add(temp); return; } for (int i = 0; i < string.length; i++) { if (isUsed[i] == true || i != 0 && isUsed[i - 1] == false && string[i] == string[i - 1]) { continue; } isUsed[i] = true; stringPermutation2Helper(result, temp + string[i], string, isUsed); // backtracking isUsed[i] = false; } } }
This is a navie version of solution. It needs extra memory which is O(n), where the n represents the length of the input string, to store the information if this char in string has been added. The time complexity of this algorithm is O(n^2).
If you want to solve this problem without extra memory space, we can use solution used in “Next Permutation”
近期评论