Last active
July 6, 2018 23:59
-
-
Save asethia/1c850c0c2561854439187fea2f1e010b to your computer and use it in GitHub Desktop.
From given string input can we make Palindrome or not
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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