LeetCode 267: Palindrome Permutation II
LeetCode 267 Solution Explanation
Explanation
To solve this problem, we need to generate all possible palindrome permutations of a given string. The approach involves counting the frequency of each character in the input string and then creating half of the palindrome string based on the even count characters. For odd count characters, we can use one character in the middle of the palindrome string. We then use backtracking to generate all permutations of the first half of the palindrome string and append the reversed string to form the final palindrome permutations.
Algorithm:
- Count the frequency of each character in the input string.
- Create the first half of the palindrome string based on even count characters and a middle character for the odd count character.
- Use backtracking to generate all permutations of the first half of the palindrome string.
- Append the reversed string to form the final palindrome permutations.
Time Complexity:
The time complexity of this algorithm is O(n * n!) where n is the length of the input string.
Space Complexity:
The space complexity of this algorithm is O(n) where n is the length of the input string.
LeetCode 267 Solutions in Java, C++, Python
class Solution {
public List<String> generatePalindromes(String s) {
List<String> result = new ArrayList<>();
Map<Character, Integer> charCount = new HashMap<>();
for (char c : s.toCharArray()) {
charCount.put(c, charCount.getOrDefault(c, 0) + 1);
}
String midChar = "";
List<Character> oddChars = new ArrayList<>();
StringBuilder firstHalf = new StringBuilder();
for (Map.Entry<Character, Integer> entry : charCount.entrySet()) {
char c = entry.getKey();
int count = entry.getValue();
if (count % 2 == 1) {
if (!midChar.isEmpty()) {
return result;
}
midChar = String.valueOf(c);
count--;
}
for (int i = 0; i < count / 2; i++) {
firstHalf.append(c);
}
if (count % 2 == 1) {
oddChars.add(c);
}
}
generatePermutations(firstHalf.toString().toCharArray(), 0, midChar, result);
for (int i = 0; i < result.size(); i++) {
StringBuilder reversed = new StringBuilder(result.get(i)).reverse();
result.set(i, result.get(i) + midChar + reversed);
}
return result;
}
private void generatePermutations(char[] arr, int index, String midChar, List<String> result) {
if (index == arr.length) {
result.add(new String(arr));
} else {
for (int i = index; i < arr.length; i++) {
if (!containsDuplicate(arr, index, i)) {
swap(arr, index, i);
generatePermutations(arr, index + 1, midChar, result);
swap(arr, index, i);
}
}
}
}
private boolean containsDuplicate(char[] arr, int start, int end) {
for (int i = start; i < end; i++) {
if (arr[i] == arr[end]) {
return true;
}
}
return false;
}
private void swap(char[] arr, int i, int j) {
char temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}Interactive Code Editor for LeetCode 267
Improve Your LeetCode 267 Solution
Use the editor below to refine the provided solution for LeetCode 267. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...