Skip to content

Instantly share code, notes, and snippets.

@asethia
Last active July 6, 2018 23:59
Show Gist options
  • Save asethia/1c850c0c2561854439187fea2f1e010b to your computer and use it in GitHub Desktop.
Save asethia/1c850c0c2561854439187fea2f1e010b to your computer and use it in GitHub Desktop.
From given string input can we make Palindrome or not
import scala.annotation.tailrec
/**
* From given string input can we make Palindrome or not
* Input: Tact Coa
* Output: True
* (permutations: "taco cat". "atco cta". etc.)
* Created by Arun Sethia on 7/6/18.
*/
trait PalindromePermutation {
/**
* remove trail space O(n+n)=O(2n)
*
* @param in
* @return
*/
private def removeSpaceAndLowerCase(in: String): List[Char] = {
in.toList.foldLeft(new StringBuilder)(
(s, c) => if (c != ' ') s.append(c.toLower) else s)
.toList
}
/**
* Permute Palindrome is possible
*
* @param in
*/
def canPermutePalindrome(in: String): Boolean = {
val charCount: Array[Int] = Array.ofDim[Int](128)
@tailrec
def isPossible(chars: List[Char], count: Int): Int = {
chars match {
case Nil => count
case h :: t => {
val charInt = h.toInt
charCount(charInt) = charCount(charInt) + 1
val evenOddCount = if (charCount(charInt) % 2 == 0) count - 1 else count + 1
isPossible(t, evenOddCount)
}
}
}
isPossible(removeSpaceAndLowerCase(in), 0) <= 1
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment