Word ordering for formpalindrome
Hi I am trying to form palindromes from this input:
String[] text ={"ivcci", "oyotta", "cecarar","bbb","babbbb"};
getPalindrome(text);
and I need to rearrange all the words in the array to produce this output
civic
-1
rececar
bbb
bbabb
the method expects to receive an array of strings such as
public static String getPalindrome(String[] text){}
"return -1 means i." oyotta " in array can't form palíndrome
I tested this code and it works, but ig "cecarar" doesn't produce "race car" since I'm a bit new to java. I have used String for array of strings, can anyone help to spell this code correctly please?
Thank you so much!
public static String getPalindrome(String s) {
if (s == null)
return null;
Map<Character, Integer> letters = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!letters.containsKey(c))
letters.put(c, 1);
else
letters.put(c, letters.get(c) + 1);
}
char[] result = new char[s.length()];
int i = 0, j = result.length - 1;
Character middle = null;
for (Entry<Character, Integer> e : letters.entrySet()) {
int val = e.getValue();
char c = e.getKey();
if (val % 2 != 0) {
if (middle == null && s.length() % 2 != 0) {
middle = c;
val--;
} else
return "-1";
}
for (int k = 0; k < val / 2; k++) {
result[i++] = c;
result[j--] = c;
}
}
if (middle != null)
result[result.length / 2] = middle;
return new String(result);
}
source to share
For a character set to be able to create a palindrome, only one of the letters can be repeated an odd number of times, so you can rip that off first.
Without writing the actual code for you, here is the algorithm I would use:
Create a symbol map for the counter. Possible to do int[] counts = new int[26];
Go through each character on the input line and increment the counter: ++counts[Character.toLower(c)-'a'];
Then step through each character and see if it is odd if (counts[i] & 1 != 0) { if (oddIndex != -1) { return -1; } oddIndex=i; }
. This will return -1 if there are two or more odd numbers. Then you can create a StringBuilder and start with oddIndex in the middle if it exists. Then go to counts and add count [i] / 2 to the beginning and back of your string builder.
This will give you a symmetrical string from the original inputs.
Now, if you really want words, then you need a palindrome dictionary. You can preprocess all palindromes to have a "sorted character string" => "palindrome" map
class PalindromeChecker
{
final Map<String, String> palindromes = new HashMap<String, String>();
public PalindromeChecker(Iterable<String> allPalindromes) {
for (String palindrome: allPalindromes) {
char[] chars = palindrome.getChars();
Arrays.sort(chars);
palindromes.put(String.valueOf(chars), palindromes);
}
}
public String getPalindrome(String input) {
char[] chars = input.getChars();
Arrays.sort(chars);
return palindromes.get(String.valueOf(chars));
}
}
source to share
As other users have pointed out, a string can only be reordered as a palindrome if no more than one character appears an odd number of times.
Once you confirm that the string can be converted to a palindrome, you can construct a palindrome like this (this is, of course, one of many methods):
- place on the sides of the line all the pairs of characters you can get
- we put a single character in the middle of the line, which is not taken into account, if there is such a character.
Example:
public class Palindromes {
public static void main(String[] args) {
String[] text = {"ivcci", "oyotta", "cecarar","bbb","babbbb"};
for(String str : text){
evaluatePalindrome(str);
}
}
private static void evaluatePalindrome(String str){
PalindromeCandidate pc = new PalindromeCandidate(str);
if(pc.isPalindrome()){
System.out.println(pc.getPalindrome());
} else {
System.out.println("-1");
}
}
}
public class PalindromeCandidate {
private final CharacterCount characterCount;
public PalindromeCandidate(String originalString) {
this.characterCount = new CharacterCount(originalString);
}
public boolean isPalindrome(){
Collection<Integer> counts = characterCount.asMap().values();
int oddCountOccurrences = 0;
for(Integer count : counts){
oddCountOccurrences += (count%2);
}
return (oddCountOccurrences <= 1);
}
public String getPalindrome(){
if(!isPalindrome()){
throw new RuntimeException("Cannot be rearranged as a palindrome.");
}
Map<Character, Integer> counts = characterCount.asMap();
StringBuilder leftSide = new StringBuilder();
StringBuilder middle = new StringBuilder();
for(Character ch : counts.keySet()){
int occurrences = counts.get(ch);
while(occurrences > 1){
leftSide.append(ch);
occurrences -= 2;
}
if(occurrences > 0){
middle.append(ch);
}
}
StringBuilder rightSide = new StringBuilder(leftSide).reverse();
return leftSide.append(middle).append(rightSide).toString();
}
}
/**
* Thin wrapper around a Map<Character, Integer>. Used for counting occurences
* of characters.
*/
public class CharacterCount {
private final Map<Character, Integer> map;
public CharacterCount(String str) {
this.map = new HashMap<>();
for(Character ch : str.toCharArray()){
increment(ch);
}
}
private void increment(Character ch){
this.map.put(ch, getCount(ch) + 1);
}
private Integer getCount(Character ch){
if(map.containsKey(ch)){
return map.get(ch);
} else {
return 0;
}
}
public Map<Character, Integer> asMap(){
return new HashMap<>(map);
}
}
source to share