![]() ![]() There’s little chance of us optimising the runtime of this algorithm, but we can clean it up.Ī potential optimisation would be to check the odd counts as we build up the table, and then simply return at the end if we have more than 1 odd character: ![]() I am not a Big O expert by any stretch of the imagination, but what we do know is that any algorithm will always need to visit every character in the input string. if we get to here, then either all the characters have an even number of occurrences, or we only have a _single_ odd count set foundOdd to 'true' - if we find _another_ odd count, this can't be a palindrome if we've previously found an odd count, this cannot be a palindrome, so return 'false' if the count is an even number, skip this iteration declare a temporary variable to tell us if we've found any odd counts yet the table doesn't yet contain this character, so add it with a count of 1 the table contains this character already, so increment the count convert the character to its lowercase representation iterate over the string and build the Dictionary create a dictionary of to hold the count of each character Public static bool IsPermutation( string input) strings with an odd number of characters must have at most one character with an odd countĪ naïve solution would be to build up a hash table of all characters and their counts, e.g.:.strings with an even number of characters must have even counts for all characters.This means that we can rearrange the characters into a palindrome by balancing all the even numbered characters either side of the odd numbered character. ![]() We have 2 of all characters apart from o. In order to be able to write the characters the same forwards and backwards then we need to have an even number for all characters (when we have an even number of characters), or we can at most one character for which there is an odd number. To determine if a string is a permutation of a palindrome, we need to know if the characters can be arranged such that they can be written the same forwards and backwards. The solutions found in this article are adapted from Cracking The Coding Interview which provides code samples in Java. output: true (permutations: tacocat, atcocta, actoact, etc.).The palindrome does not need to be limited to just dictionary words. Given a string, write a function to check if it is a permutation of a palindrome.Ī palindrome is a word or phrase that is the same forwards and backwards.Ī permutation is a rearrangement of letters/characters. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |