Last active
October 23, 2023 17:34
-
-
Save atierian/18a64b0d9f16028437ca0883d2c644ae to your computer and use it in GitHub Desktop.
misguided (but fun) attempt at a fast path check for Palidrone Permutations problem
This file contains 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
/* | |
Palindrome Permutation: given a string, write a function to check if it is a permutation of a palindrome. | |
A palindrome is a word or phrase that is the same forwards and backwards. | |
A permutation is a rearrangement of letters. | |
The palindrome does not need to be limited to just dictionary words. | |
You can ignore casing and non-letter characters. | |
EXAMPLE | |
Input: Tact Coa | |
Output: True (permutations: “taco cat”, “atco cta”, etc.) | |
*/ | |
func palindromePermutation(s: String) -> Bool { | |
// 2 or fewer characters are always | |
// a palindrome permutation. | |
guard s.count > 2 else { return true } | |
let asciiValues = s | |
.lazy | |
.filter(\.isLetter) | |
.flatMap { $0.lowercased() } | |
.compactMap(\.asciiValue) | |
let xord = asciiValues.reduce(0, ^) | |
// each character in `s` appears an even number of times | |
if xord == 0 { return true } | |
// > 1 unique characters appears odd # of times. | |
// If this condition is false, then it is definitely | |
// not a palindrome permutation. | |
// It is, however, prone to false positives | |
// Note: 97...122 represents "a"..."z" ascii values. | |
if !(97...122 ~= xord) { return false } | |
// Fast path doesn't cover some cases where several | |
// unique characters occurr an odd # of times. | |
// We already checked the 0 case above; at this point | |
// we're just confirming that there's exactly one character | |
// appearing an odd # of times. | |
return asciiValues.reduce(into: Set<UInt8>()) { set, ascii in | |
if !set.insert(ascii).inserted { | |
set.remove(ascii) | |
} | |
}.count == 1 | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment