我在考虑这个方法: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
这是我的解决方案。字符串可能包含多个带有空格的单词,例如:
输入:Tact Coa
输出:true
输入:Tact Coa vvu
输出:false
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;
}
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");
}
}
任何字符串只有在最多一个字符出现奇数次且所有其他字符必须出现偶数次时才能成为回文。以下程序可用于检查一个字符串是否可以成为回文。
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;
}
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")
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;
}
这是我的代码:
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;
}
for (int c: s.codepoints())
。用于“计算元素”的习惯用法可能是stCount.merge(c, 1, Integer::sum)
。当您不需要键时,只需迭代stCount.values()
。 - greybeard使用JAVA
import java.util.*;
import java.lang.*;
//Classs
class Permutation {
/*
* We need to have an even number of almost all characters,
* so that half can be on one side and half can be on the other side.
* At most one character (the middle character) can have an odd count.
*/
public static boolean hasPalindrome(String str) {
boolean wasOdd = false;
for (Character c: str.toCharArray()) {
int counter = 0;
for (Character cc: str.toCharArray()) {
if (c == cc) {
counter++;
}
}
if (counter % 2 == 1) {
if (wasOdd) {
return false;
}
wasOdd = true;
}
}
return true;
}
public static void main(String args[]) throws Exception {
//Taking string input
//Scanner
Scanner s = new Scanner(System.in);
String str = s.nextLine();
if (Permutation.hasPalindrome(str)) {
System.out.println("YES"); // Writing output to STDOUT
} else {
System.out.println("NO"); // Writing output to STDOUT
}
}
}
为什么要使用后缀树或任何其他数据结构?
回文字符串的基本要求是:所有字符的频率必须是偶数,或者只能有一个字符的频率是奇数。
示例:
输入: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
}
我们也可以通过集合来实现这个目标
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");
}
}
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;
}