检查字符串的排列是否可以成为回文
Check if a permutation of a string can become a palindrome
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)#
- 检查同一节点的所有排列
我错过了什么吗？
如果我没有正确理解你的问题，我是这样理解的：
If the input string can be rearranged into a palindrome, output "True", otherwise output "False".
那么您可以使用这些简单的规则：
- 如果长度为偶数，则输入中的每个唯一字符都必须出现 2 次的倍数。
- 如果长度为奇数，则除 1 之外的每个唯一字符都必须出现 2 次的倍数。只允许1个字符不出现2次的倍数。
因此对于给出的 3 个示例：
"mmo"，奇数长度，m出现两次（2的倍数），o出现一次（不是2的倍数），所以True.
"yakak"，奇数长度，a出现两次（2的倍数），k出现两次（2的倍数），y出现一次（不是a 2) 的倍数，所以 True.
"travel",不止一个字符不会出现2的倍数，所以False.
其他示例：
"mmorpg"，只有m出现2的倍数，其余只出现一次，所以False.
"mmom"，没有字符出现2的倍数，多于一个字符出现"not a multiple of 2 times"，所以False.
此时你应该意识到，如果只允许1个字符出现非2的倍数，那么你可以忽略长度。长度为偶数的字符串将有 2 个或更多字符出现非 2 的倍数，或者根本 none。
所以最终规则应该是这样的：
If at most 1 unique character occurs a non-multiple-of-2 times in the input, the output is True otherwise the output is False.
实际上，您要查找的只是所有（或除一个以外的）字母是否配对。只要是，就可以变成回文。
所以它会像...
bool canBeTurnedIntoAPalindrome(string drome)
{
// If we've found a letter that has no match, the center letter.
bool centerUsed = false;
char center;
char c;
int count = 0;
// TODO: Remove whitespace from the string.
// Check each letter to see if there's an even number of it.
for(int i = 0; i<drome.length(); i++)
{
c = drome[i];
count = 0;
for(int j = 0; j < drome.length(); j++)
if (drome[j] == c)
count++;
// If there was an odd number of those entries
// and the center is already used, then a palindrome
// is impossible, so return false.
if (count % 2 == 1)
{
if (centerUsed == true && center != c)
return false;
else
{
centerused = true;
center = c; // This is so when we encounter it again it
// doesn't count it as another separate center.
}
}
}
// If we made it all the way through that loop without returning false, then
return true;
}
这不是最有效的（它计算遇到的字母的次数，即使它们已经被计算过），但它确实有效。
您需要做的就是检查最多有一个字符出现次数为奇数。这是一个 Java 示例：
private static boolean canMakePalindrom(String s) {
Map<Character, Integer> countChars = new HashMap<>();
// Count the occurrences of each character
for (char c : s.toCharArray()) {
Integer count = countChars.get(c);
if (count == null) {
count = Integer.valueOf(1);
} else {
count = count + 1;
}
countChars.put(c, count);
}
boolean hasOdd = false;
for (int count : countChars.values()) {
if (count % 2 == 1) {
if (hasOdd) {
// Found two chars with odd counts - return false;
return false;
} else {
// Found the first char with odd count
hasOdd = true;
}
}
}
// Haven't found more than one char with an odd count
return true;
}
EDIT4（是的 - 这些是为了有意义而排序的，但按时间顺序编号）：
上面的实现有一个内置的低效率。我不认为可以避免对字符串的第一次迭代，但是没有真正的理由去计算所有出现的次数——只跟踪那些出现奇数的次数就足够了。对于这个用例，跟踪我们遇到的每个字符（例如 Set）并在我们再次遇到它时将其删除就足够了。在最坏的情况下，字符串中的所有字符都不同，性能是相当的，但在常见的情况下，每个字符多次出现，这种实现提高了第二个循环的时间和内存复杂度（这是现在减少到一个条件）显着：
private static boolean canMakePalindrom(String s) {
Set<Character> oddChars = new HashSet<>();
// Go over the characters
for (char c : s.toCharArray()) {
// Record the encountered character:
if (!oddChars.add(c)) {
// If the char was already encountered, remove it -
// this is an even time we encounter it
oddChars.remove(c);
}
}
// Check the number of characters with odd counts:
return oddChars.size() <= 1;
}
EDIT3（是的 - 这些是为了有意义而排序的，但按时间顺序编号）：
Java 8 提供了流畅的流 API，可用于创建类似于下面 Python 单行代码的实现：
private static boolean canMakePalindrom(String s) {
return s.chars()
.boxed()
.collect(Collectors.groupingBy(Function.identity(),
Collectors.counting()))
.values()
.stream()
.filter(p -> p % 2 == 1)
.count() <= 1;
}
编辑：
Python 内置函数和理解能力使它太有吸引力了，不能不发布这个线性解决方案。它可能比前面提到的 Java 效率低，但非常优雅：
from collections import Counter
def canMakePalindrom(s):
return len([v for v in Counter(s).values() if v % 2 == 1]) <= 1
编辑 2：
或者，@DSM 在评论中提出的更简洁的方法：
from collections import Counter
def canMakePalindrom(s):
return sum(v % 2 == 1 for v in Counter(s).values()) <= 1
另一种方法不是计算每个字母出现的次数，而是跟踪字母出现的次数是奇数次还是偶数次。如果一个字母出现了偶数次，则无需担心，只需跟踪一组中出现的奇数次即可。在 Java:
public static boolean canMakePalindrome(String s) {
Set<Character> oddLetters = new HashSet<>();
for ( char c : s.toCharArray() ) {
if ( ! oddLetters.remove(c) ) {
oddLetters.add(c);
}
}
return oddLetters.size() <= 1;
}
我的想法是，如果奇数个字母的个数是一个，其余的都是偶数，那么回文是可能的..这是我在Python
中的程序
string = raw_input()
found = False
char_set = set(string) # Lets find unique letters
d_dict = {}
for c in char_set:
d_dict[c] = string.count(c) # Keep count of each letter
odd_l = [e for e in d_dict.values() if e%2 == 1] # Check how many has odd number of occurrence
if len(odd_l) >1:
pass
else:
found = True
if not found:
print("NO")
else:
print("YES")
def can_permutation_palindrome(s):
counter = {}
for c in s:
counter[c] = counter.get(c, 0) + 1
odd_count = 0
for count in counter.values():
odd_count += count % 2
return odd_count in [0, 1]
任何字符串只要最多有一个字符出现奇数就可以是回文。次，所有其他字符必须出现偶数次。下面的程序可以用来判断一个回文是否可以是字符串。
void checkPalindrome(string s)
{
vector<int> vec(256,0); //Vector for all ASCII characters present.
for(int i=0;i<s.length();++i)
{
vec[s[i]-'a']++;
}
int odd_count=0,flag=0;
for(int i=0;i<vec.size();++i)
{
if(vec[i]%2!=0)
odd_count++;
if(odd_count>1)
{
flag=1;
cout<<"Can't be palindrome"<<endl;
break;
}
}
if(flag==0)
cout<<"Yes can be palindrome"<<endl;
}
复杂度为 O(n)。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace PallindromePemutation
{
class charcount
{
public char character { get; set; }
public int occurences { get; set; }
}
class Program
{
static void Main(string[] args)
{
List<charcount> list = new List<charcount>();
charcount ch;
int count = 0;
char[] arr = "travel".ToCharArray();
for (int i = 0; i < arr.Length; i++)
{
charcount res = list.Find(x => x.character == arr.ElementAt(i));
if (res == null)
{
ch = new charcount();
ch.character = arr.ElementAt(i);
ch.occurences = 1;
list.Add(ch);
}
else
{
charcount temp= list.Find(x => x.character == arr.ElementAt(i));
temp.occurences++;
}
}
foreach (var item in list)
{
if (!(item.occurences % 2 == 0))
{
count++;
}
}
if (count > 1)
{
Console.WriteLine("false");
}
else
{
Console.WriteLine("true");
}
Console.ReadKey();
}
}
}
如果我们不关心字符串中字符和空格的大小写敏感性，那么在 C# 中使用字典的示例解决方案可以是：
private static bool IsPalindromePermutation(string inputStr)
{
// First, check whether input string is null or whitespace.
// If yes, then return false.
if (string.IsNullOrWhiteSpace(inputStr))
return false;
var inputDict = new Dictionary<char, int>();
// Big/small letter is not important
var lowerInputStr = inputStr.ToLower();
// Fill input dictionary
// If hit a space, then skip it
for (var i = 0; i < lowerInputStr.Length; i++)
{
if (lowerInputStr[i] != ' ')
{
if (inputDict.ContainsKey(lowerInputStr[i]))
inputDict[lowerInputStr[i]] += 1;
else
inputDict.Add(lowerInputStr[i], 1);
}
}
var countOdds = 0;
foreach(var elem in inputDict)
{
if(elem.Value % 2 != 0)
countOdds++;
}
return countOdds <= 1;
}
def check(string):
bv = 0
for s in string:
bv ^= 1 << ord(s)
return bv == 0 or bv & (bv - 1) == 0
我们也可以通过集合来实现这一点
String name = "raa";
List<Character> temp = new ArrayList<>(name.chars()
.mapToObj(e -> (char) e).collect(Collectors.toList()));
for (int i = 0; i < temp.size(); i++) {
for (int j = i + 1; j < temp.size(); j++) {
if (temp.get(i).equals(temp.get(j))) {
temp.remove(j);
temp.remove(i);
i--;
}
}
}
if (temp.size() <= 1) {
System.out.println("Pallindrome");
} else {
System.out.println(temp.size());
System.out.println("Not Pallindrome");
}
}
这是我的解决方案
public static void main(String[] args) {
List<Character> characters = new ArrayList<>();
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
for (int i = 0; i < input.length(); i++){
char val = input.charAt(i);
if (characters.contains(val)){
characters.remove(characters.indexOf(val));
} else{
characters.add(val);
}
}
if (characters.size() == 1 || characters.size() == 0){
System.out.print("Yes");
} else{
System.out.print("No");
}
}
这就是我的解决方案。该字符串可以包含多个带空格的单词，例如
输入：Tact Coa
输出真
输入：Tact Coa vvu
输出：假
public static boolean checkForPalindrome(String str) {
String strTrimmed = str.replaceAll(" ","");
System.out.println(strTrimmed);
char[] str1 = strTrimmed.toCharArray();
for (int i = 0; i < str1.length; i++) {
str1[i] = Character.toLowerCase(str1[i]);
}
Arrays.sort(str1);
String result = new String(str1);
System.out.println(result);
int count = 0;
for (int j = 0; j < str1.length; j += 2) {
if (j != str1.length-1) {
if (str1[j] != str1[j+1]) {
count++;
j++;
}
} else {
count++;
}
}
if (count > 1) return false;
else return true;
}
我今天找到了下面的解决方案 (python)。我认为它是可读的，performance-wise它真的很好。
sum(map(lambda x: word.count(x) % 2, set(word))) <= 1
我们基本上是在计算字符串 "word" 中每个字符出现的次数，将除以 2 的余数求和，然后检查是否最多有 1 个字符。
我们的想法是，您需要将所有字符配对，但可能有一个（中间那个）除外。
问题：字符串可以变成回文吗？
方法一：字符数
在 Java 中：
public class TEST11 {
public static void main(String[] args) {
String a = "Protijayi";
int[] count = new int[256];
Arrays.fill(count, 0);
for (int i = 0; i < a.length(); i++) {
char ch = a.charAt(i);
count[ch]++;
} // for
// counting of odd letters
int odd = 0;
for (int i = 0; i < count.length; i++) {
if ((count[i] & 1) == 1) {
odd++;
}
} // for
if (odd > 1) {
System.out.println("no");
} else {
System.out.println("yes");
}
}
}
输入Python:
def fix (a):
count = [0] * 256
for i in a: count[ord(i)] += 1
# counting of odd characters
odd = 0
for i in range(256):
if((count[i] & 1) == 1): odd += 1
if(odd > 1):print("no")
else:print("yes")
a = "Protijayi"
fix(a)
方法二：HashSet的使用
在 Java:
public class TEST11 {
public static void main(String[] args) {
String a = "Protijayi";
Set<Character> set = new HashSet<>();
for (char ch : a.toCharArray()) {
if (set.contains(ch)) {
set.remove(ch);
}
set.add(ch);
} // for
if (set.size() <= 1) {
System.out.println("yes can be a palindrome");
} else {
System.out.println("no");
}
}
}
Swift 这个问题的例子。
var str = "mmoosl"
extension String {
func count(of needle: Character) -> Int {
return reduce(0) {
== needle ? [=10=] + 1 : [=10=]
}
}
}
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;
}
}
}
为什么要使用后缀树或任何其他数据结构？
回文串的基本要求是所有字符出现的频率必须是偶数 或者只有一个字符可以有奇数频率.
示例 :-
输入 : aabbaa
输出：a的频率为4，b为2（均为偶数）
输入：xxzyzxx
输出：x的频率为4，z为2且y=1（只有1个奇数）
为了更好理解的示例代码：
bool ispalin(string str) //function to check
{
int freq[26] = {0}; //to store frequency of character here i am
// considering only lower case letters
for (int i = 0; str.length(); i++)
freq[str[i]]++;
int odd = 0;
for (int i = 0; i < 26; i++) //Count odd occurring characters
{
if (freq[i] & 1) //checking if odd
odd++;
if (odd > 1) //if number of odd freq is greater than 1
return false;
}
return true; //else return true
}
python 检查给定字符串是否可以形成回文的代码:
test_str = input('enter any string = ')
count = 0
for item in set(test_str):
if test_str.count(item)%2 != 0:
count+=1
if (count>1):
print(" palindrome cannot be formed")
else:
print(" palindrome can be formed")
请尝试此代码，如有问题请评论
更高效的实施 - 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);
}
这是我的代码：
boolean palindromeRearranging(String inputString) {
HashMap<Character,Integer> stCount=new HashMap<>();
for(int i=0;i<inputString.length();i++){
stCount.put(inputString.charAt(i),0);
}
for(int i=0;i<inputString.length();i++){
int c= stCount.get(inputString.charAt(i));
stCount.put(inputString.charAt(i),++c);
}
int c=0;
for (Map.Entry<Character,Integer> entry : stCount.entrySet()){
if(entry.getValue()%2!=0){
c++;
if(c>1){
return false;
}
}
}
return true;
}
JS解决方案：
function solution(inputString) {
const arr = inputString.split('');
let hasCoupleList = arr.map( (el) => arr.filter( (el1) => el1 == el).length % 2 == 0).filter( (el) => el == false).length;
return (arr.length % 2 == 0)
? hasCoupleList == 0
: hasCoupleList == 1;
}
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)#
- 检查同一节点的所有排列
我错过了什么吗？
如果我没有正确理解你的问题，我是这样理解的：
If the input string can be rearranged into a palindrome, output "True", otherwise output "False".
那么您可以使用这些简单的规则：
- 如果长度为偶数，则输入中的每个唯一字符都必须出现 2 次的倍数。
- 如果长度为奇数，则除 1 之外的每个唯一字符都必须出现 2 次的倍数。只允许1个字符不出现2次的倍数。
因此对于给出的 3 个示例：
"mmo"，奇数长度，m出现两次（2的倍数），o出现一次（不是2的倍数），所以True.
"yakak"，奇数长度，a出现两次（2的倍数），k出现两次（2的倍数），y出现一次（不是a 2) 的倍数，所以 True.
"travel",不止一个字符不会出现2的倍数，所以False.
其他示例：
"mmorpg"，只有m出现2的倍数，其余只出现一次，所以False.
"mmom"，没有字符出现2的倍数，多于一个字符出现"not a multiple of 2 times"，所以False.
此时你应该意识到，如果只允许1个字符出现非2的倍数，那么你可以忽略长度。长度为偶数的字符串将有 2 个或更多字符出现非 2 的倍数，或者根本 none。
所以最终规则应该是这样的：
If at most 1 unique character occurs a non-multiple-of-2 times in the input, the output is
Trueotherwise the output isFalse.
实际上，您要查找的只是所有（或除一个以外的）字母是否配对。只要是，就可以变成回文。
所以它会像...
bool canBeTurnedIntoAPalindrome(string drome)
{
// If we've found a letter that has no match, the center letter.
bool centerUsed = false;
char center;
char c;
int count = 0;
// TODO: Remove whitespace from the string.
// Check each letter to see if there's an even number of it.
for(int i = 0; i<drome.length(); i++)
{
c = drome[i];
count = 0;
for(int j = 0; j < drome.length(); j++)
if (drome[j] == c)
count++;
// If there was an odd number of those entries
// and the center is already used, then a palindrome
// is impossible, so return false.
if (count % 2 == 1)
{
if (centerUsed == true && center != c)
return false;
else
{
centerused = true;
center = c; // This is so when we encounter it again it
// doesn't count it as another separate center.
}
}
}
// If we made it all the way through that loop without returning false, then
return true;
}
这不是最有效的（它计算遇到的字母的次数，即使它们已经被计算过），但它确实有效。
您需要做的就是检查最多有一个字符出现次数为奇数。这是一个 Java 示例：
private static boolean canMakePalindrom(String s) {
Map<Character, Integer> countChars = new HashMap<>();
// Count the occurrences of each character
for (char c : s.toCharArray()) {
Integer count = countChars.get(c);
if (count == null) {
count = Integer.valueOf(1);
} else {
count = count + 1;
}
countChars.put(c, count);
}
boolean hasOdd = false;
for (int count : countChars.values()) {
if (count % 2 == 1) {
if (hasOdd) {
// Found two chars with odd counts - return false;
return false;
} else {
// Found the first char with odd count
hasOdd = true;
}
}
}
// Haven't found more than one char with an odd count
return true;
}
EDIT4（是的 - 这些是为了有意义而排序的，但按时间顺序编号）：
上面的实现有一个内置的低效率。我不认为可以避免对字符串的第一次迭代，但是没有真正的理由去计算所有出现的次数——只跟踪那些出现奇数的次数就足够了。对于这个用例，跟踪我们遇到的每个字符（例如 Set）并在我们再次遇到它时将其删除就足够了。在最坏的情况下，字符串中的所有字符都不同，性能是相当的，但在常见的情况下，每个字符多次出现，这种实现提高了第二个循环的时间和内存复杂度（这是现在减少到一个条件）显着：
private static boolean canMakePalindrom(String s) {
Set<Character> oddChars = new HashSet<>();
// Go over the characters
for (char c : s.toCharArray()) {
// Record the encountered character:
if (!oddChars.add(c)) {
// If the char was already encountered, remove it -
// this is an even time we encounter it
oddChars.remove(c);
}
}
// Check the number of characters with odd counts:
return oddChars.size() <= 1;
}
EDIT3（是的 - 这些是为了有意义而排序的，但按时间顺序编号）：
Java 8 提供了流畅的流 API，可用于创建类似于下面 Python 单行代码的实现：
private static boolean canMakePalindrom(String s) {
return s.chars()
.boxed()
.collect(Collectors.groupingBy(Function.identity(),
Collectors.counting()))
.values()
.stream()
.filter(p -> p % 2 == 1)
.count() <= 1;
}
编辑：
Python 内置函数和理解能力使它太有吸引力了，不能不发布这个线性解决方案。它可能比前面提到的 Java 效率低，但非常优雅：
from collections import Counter
def canMakePalindrom(s):
return len([v for v in Counter(s).values() if v % 2 == 1]) <= 1
编辑 2：
或者，@DSM 在评论中提出的更简洁的方法：
from collections import Counter
def canMakePalindrom(s):
return sum(v % 2 == 1 for v in Counter(s).values()) <= 1
另一种方法不是计算每个字母出现的次数，而是跟踪字母出现的次数是奇数次还是偶数次。如果一个字母出现了偶数次，则无需担心，只需跟踪一组中出现的奇数次即可。在 Java:
public static boolean canMakePalindrome(String s) {
Set<Character> oddLetters = new HashSet<>();
for ( char c : s.toCharArray() ) {
if ( ! oddLetters.remove(c) ) {
oddLetters.add(c);
}
}
return oddLetters.size() <= 1;
}
我的想法是，如果奇数个字母的个数是一个，其余的都是偶数，那么回文是可能的..这是我在Python
中的程序string = raw_input()
found = False
char_set = set(string) # Lets find unique letters
d_dict = {}
for c in char_set:
d_dict[c] = string.count(c) # Keep count of each letter
odd_l = [e for e in d_dict.values() if e%2 == 1] # Check how many has odd number of occurrence
if len(odd_l) >1:
pass
else:
found = True
if not found:
print("NO")
else:
print("YES")
def can_permutation_palindrome(s):
counter = {}
for c in s:
counter[c] = counter.get(c, 0) + 1
odd_count = 0
for count in counter.values():
odd_count += count % 2
return odd_count in [0, 1]
任何字符串只要最多有一个字符出现奇数就可以是回文。次，所有其他字符必须出现偶数次。下面的程序可以用来判断一个回文是否可以是字符串。
void checkPalindrome(string s)
{
vector<int> vec(256,0); //Vector for all ASCII characters present.
for(int i=0;i<s.length();++i)
{
vec[s[i]-'a']++;
}
int odd_count=0,flag=0;
for(int i=0;i<vec.size();++i)
{
if(vec[i]%2!=0)
odd_count++;
if(odd_count>1)
{
flag=1;
cout<<"Can't be palindrome"<<endl;
break;
}
}
if(flag==0)
cout<<"Yes can be palindrome"<<endl;
}
复杂度为 O(n)。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace PallindromePemutation
{
class charcount
{
public char character { get; set; }
public int occurences { get; set; }
}
class Program
{
static void Main(string[] args)
{
List<charcount> list = new List<charcount>();
charcount ch;
int count = 0;
char[] arr = "travel".ToCharArray();
for (int i = 0; i < arr.Length; i++)
{
charcount res = list.Find(x => x.character == arr.ElementAt(i));
if (res == null)
{
ch = new charcount();
ch.character = arr.ElementAt(i);
ch.occurences = 1;
list.Add(ch);
}
else
{
charcount temp= list.Find(x => x.character == arr.ElementAt(i));
temp.occurences++;
}
}
foreach (var item in list)
{
if (!(item.occurences % 2 == 0))
{
count++;
}
}
if (count > 1)
{
Console.WriteLine("false");
}
else
{
Console.WriteLine("true");
}
Console.ReadKey();
}
}
}
如果我们不关心字符串中字符和空格的大小写敏感性，那么在 C# 中使用字典的示例解决方案可以是：
private static bool IsPalindromePermutation(string inputStr)
{
// First, check whether input string is null or whitespace.
// If yes, then return false.
if (string.IsNullOrWhiteSpace(inputStr))
return false;
var inputDict = new Dictionary<char, int>();
// Big/small letter is not important
var lowerInputStr = inputStr.ToLower();
// Fill input dictionary
// If hit a space, then skip it
for (var i = 0; i < lowerInputStr.Length; i++)
{
if (lowerInputStr[i] != ' ')
{
if (inputDict.ContainsKey(lowerInputStr[i]))
inputDict[lowerInputStr[i]] += 1;
else
inputDict.Add(lowerInputStr[i], 1);
}
}
var countOdds = 0;
foreach(var elem in inputDict)
{
if(elem.Value % 2 != 0)
countOdds++;
}
return countOdds <= 1;
}
def check(string):
bv = 0
for s in string:
bv ^= 1 << ord(s)
return bv == 0 or bv & (bv - 1) == 0
我们也可以通过集合来实现这一点
String name = "raa";
List<Character> temp = new ArrayList<>(name.chars()
.mapToObj(e -> (char) e).collect(Collectors.toList()));
for (int i = 0; i < temp.size(); i++) {
for (int j = i + 1; j < temp.size(); j++) {
if (temp.get(i).equals(temp.get(j))) {
temp.remove(j);
temp.remove(i);
i--;
}
}
}
if (temp.size() <= 1) {
System.out.println("Pallindrome");
} else {
System.out.println(temp.size());
System.out.println("Not Pallindrome");
}
}
这是我的解决方案
public static void main(String[] args) {
List<Character> characters = new ArrayList<>();
Scanner scanner = new Scanner(System.in);
String input = scanner.nextLine();
for (int i = 0; i < input.length(); i++){
char val = input.charAt(i);
if (characters.contains(val)){
characters.remove(characters.indexOf(val));
} else{
characters.add(val);
}
}
if (characters.size() == 1 || characters.size() == 0){
System.out.print("Yes");
} else{
System.out.print("No");
}
}
这就是我的解决方案。该字符串可以包含多个带空格的单词，例如
输入：Tact Coa
输出真
输入：Tact Coa vvu
输出：假
public static boolean checkForPalindrome(String str) {
String strTrimmed = str.replaceAll(" ","");
System.out.println(strTrimmed);
char[] str1 = strTrimmed.toCharArray();
for (int i = 0; i < str1.length; i++) {
str1[i] = Character.toLowerCase(str1[i]);
}
Arrays.sort(str1);
String result = new String(str1);
System.out.println(result);
int count = 0;
for (int j = 0; j < str1.length; j += 2) {
if (j != str1.length-1) {
if (str1[j] != str1[j+1]) {
count++;
j++;
}
} else {
count++;
}
}
if (count > 1) return false;
else return true;
}
我今天找到了下面的解决方案 (python)。我认为它是可读的，performance-wise它真的很好。
sum(map(lambda x: word.count(x) % 2, set(word))) <= 1
我们基本上是在计算字符串 "word" 中每个字符出现的次数，将除以 2 的余数求和，然后检查是否最多有 1 个字符。
我们的想法是，您需要将所有字符配对，但可能有一个（中间那个）除外。
问题：字符串可以变成回文吗？ 方法一：字符数 在 Java 中：
public class TEST11 {
public static void main(String[] args) {
String a = "Protijayi";
int[] count = new int[256];
Arrays.fill(count, 0);
for (int i = 0; i < a.length(); i++) {
char ch = a.charAt(i);
count[ch]++;
} // for
// counting of odd letters
int odd = 0;
for (int i = 0; i < count.length; i++) {
if ((count[i] & 1) == 1) {
odd++;
}
} // for
if (odd > 1) {
System.out.println("no");
} else {
System.out.println("yes");
}
}
}
输入Python:
def fix (a):
count = [0] * 256
for i in a: count[ord(i)] += 1
# counting of odd characters
odd = 0
for i in range(256):
if((count[i] & 1) == 1): odd += 1
if(odd > 1):print("no")
else:print("yes")
a = "Protijayi"
fix(a)
方法二：HashSet的使用 在 Java:
public class TEST11 {
public static void main(String[] args) {
String a = "Protijayi";
Set<Character> set = new HashSet<>();
for (char ch : a.toCharArray()) {
if (set.contains(ch)) {
set.remove(ch);
}
set.add(ch);
} // for
if (set.size() <= 1) {
System.out.println("yes can be a palindrome");
} else {
System.out.println("no");
}
}
}
Swift 这个问题的例子。
var str = "mmoosl"
extension String {
func count(of needle: Character) -> Int {
return reduce(0) {
== needle ? [=10=] + 1 : [=10=]
}
}
}
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;
}
}
}
为什么要使用后缀树或任何其他数据结构？
回文串的基本要求是所有字符出现的频率必须是偶数 或者只有一个字符可以有奇数频率.
示例 :-
输入 : aabbaa
输出：a的频率为4，b为2（均为偶数）
输入：xxzyzxx
输出：x的频率为4，z为2且y=1（只有1个奇数）
为了更好理解的示例代码：
bool ispalin(string str) //function to check
{
int freq[26] = {0}; //to store frequency of character here i am
// considering only lower case letters
for (int i = 0; str.length(); i++)
freq[str[i]]++;
int odd = 0;
for (int i = 0; i < 26; i++) //Count odd occurring characters
{
if (freq[i] & 1) //checking if odd
odd++;
if (odd > 1) //if number of odd freq is greater than 1
return false;
}
return true; //else return true
}
python 检查给定字符串是否可以形成回文的代码:
test_str = input('enter any string = ')
count = 0
for item in set(test_str):
if test_str.count(item)%2 != 0:
count+=1
if (count>1):
print(" palindrome cannot be formed")
else:
print(" palindrome can be formed")
请尝试此代码，如有问题请评论
更高效的实施 - 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);
}
这是我的代码：
boolean palindromeRearranging(String inputString) {
HashMap<Character,Integer> stCount=new HashMap<>();
for(int i=0;i<inputString.length();i++){
stCount.put(inputString.charAt(i),0);
}
for(int i=0;i<inputString.length();i++){
int c= stCount.get(inputString.charAt(i));
stCount.put(inputString.charAt(i),++c);
}
int c=0;
for (Map.Entry<Character,Integer> entry : stCount.entrySet()){
if(entry.getValue()%2!=0){
c++;
if(c>1){
return false;
}
}
}
return true;
}
JS解决方案：
function solution(inputString) {
const arr = inputString.split('');
let hasCoupleList = arr.map( (el) => arr.filter( (el1) => el1 == el).length % 2 == 0).filter( (el) => el == false).length;
return (arr.length % 2 == 0)
? hasCoupleList == 0
: hasCoupleList == 1;
}