Determine if a string is a palindrome
A palindrome is a string that reads the same forward and backward, for example, radar, toot, and madam. In this lesson we discuss how to approach the palindrome problem using TypeScript / JavaScript.
We also discuss a more complex algorithmic challenge of writing a function to check if any permutation of a given string is a palindrome.
[00:00] Here we have a requirement to determine if the string is a palindrome. We will start by creating our isPalindrome function. It takes the string and returns a Boolean which is true if the string is a palindrome, or false if it isn't.
[00:19] To check if the string is a palindrome, we need to check it against its reverse. To get the reverse of the string, you split the string into an array of characters, reverse this array, and finally join back this reversed array into a single string. Now, we simply check if the reversed value is equal to the original value, and return it.
[00:43] If they are equal, then the string would be a palindrome. A more complex algorithmic challenge commonly presented after isPalindrome is to write a function to check if any permutation of the given string is a palindrome. For example, the word "civic" is a palindrome.
[01:04] Therefore, any permutation of the same characters, for example, "vicic" would also be a palindrome. Similarly, since "toot" is a palindrome, so is "toto." A non-example would be the characters of the word "civil." We start off by creating the isanyPermutationPalindrome function, which will take a string and return a Boolean.
[01:30] A simple implementation would be to simply check all the permutations of the string, and if any of those are a palindrome, we would return true. However, in this naïve implementation, the runtime complexity will be driven by the permutations function, which is of the order and pictorial wherein it's the number of characters in the string.
[01:55] We can do better. The insight to a better solution is to realize that a pattern exists among the characters of any palindrome string. Civic is a palindrome, as it has C on both sides, followed by an I, and an unmatched middle V.
[02:16] The same pattern would hold for any set of characters that can form a palindrome. All characters must be paired off except one, which is allowed to be left unpaired. The characters of civil cannot form a palindrome, as both V and L would be unmatched.
[02:37] This reduces our requirement to a simple character pairing problem. We can try character pairing using a simple string set. We split the string into its characters. For each character, if it is in the current unmatched set, then great, we can delete it as it is not matched.
[03:00] If it isn't already there, then we simply add it. Finally, after we have gone through all the characters, we simply check the count of the entries. The characters of the string can form a palindrome if the count of unpaired characters is zero or one.
[03:19] This implementation simply loops through the characters of the string and does a lenient amount of work in each iteration. Therefore, its runtime is of the order N, where N is the number of characters in the string.