我在考虑这个方法:Write a method to test if a string meets the preconditions to become a palindrome.
Eg:
Input | Output mmo | True yakak | True travel | False
- 为T的所有排列制作后缀树,使得T$Reverse(T)#
- 检查相同节点的所有排列
我在考虑这个方法:Write a method to test if a string meets the preconditions to become a palindrome.
Eg:
Input | Output mmo | True yakak | True travel | False
更高效的实现 - Java
boolean palindromeRearranging(String inputString) {
Map<Character, Integer> charsCount = new HashMap<Character, Integer>();
for(char c : inputString.toCharArray()){
charsCount.compute(c, (key, val) -> val == null ? 1 : val + 1);
}
List<Integer> result = new ArrayList<>();
charsCount.forEach((k, v) -> {
if(v % 2 != 0){
result.add(v);
}
});
return (result.size() == 0 || result.size() == 1);
}
这个问题的Swift示例。
var str = "mmoosl"
extension String {
func count(of needle: Character) -> Int {
return reduce(0) {
$1 == needle ? $0 + 1 : $0
}
}
}
func canBeTurnedIntoAPalinpolyString(_ polyString: String) -> Bool {
var centerUsed = false
var center = Character("a")
for i in polyString {
let count = polyString.count(of: i)
if count == 1 && !centerUsed {
center = i
centerUsed = true
} else {
if count % 2 != 0 {
return false
}
}
}
return true
}
print(canBeTurnedIntoAPalinpolyString(str))
Java
private static boolean isStringPalindromePermutation(String input) {
if(input == null) return false;
if(input.isEmpty()) return false;
int checker = 0;
for (int i = 0; i < input.length(); i++) {
int character = input.charAt(i) - 'a';
int oneShiftedByNumberInCharacter = 1 << character;
int summaryAnd = checker & oneShiftedByNumberInCharacter;
if ( summaryAnd > 0 ) {
int revertToShiftedByChar = ~oneShiftedByNumberInCharacter;
checker = checker & revertToShiftedByChar;
} else {
checker |= oneShiftedByNumberInCharacter;
}
}
if ( input.length() % 2 == 0 ) {
if ( checker == 0) {
return true;
}
else return false;
} else {
int checkerMinusOne = checker-1;
if((checkerMinusOne & checker) == 0){
return true;
}else{
return false;
}
}
}
从检查字符串是否为回文排列实现
时间复杂度本质上是O(n)。这意味着该函数在输入字符串的长度上是线性的。
public static boolean isPermutationOfPalindrome(String str) {
// Convert the input string to lower case and remove any non-letter characters
str = str.toLowerCase().replaceAll("[^a-z]", "");
// Create an array to count the frequency of each letter
int[] charCounts = new int[26];
for (int i = 0; i < str.length(); i++) {
charCounts[str.charAt(i) - 'a']++;
}
// Check if there is at most one character with an odd frequency
boolean foundOdd = false;
for (int count : charCounts) {
if (count % 2 == 1) {
if (foundOdd) {
return false;
}
foundOdd = true;
}
}
return true;
}