Join egghead, unlock knowledge.

Want more egghead? It's 45% off for a limited time only!

This lesson is for members. Join us? Get access to all 3,000+ tutorials + a community with expert developers around the world.

Unlock All Content for 45% Off

Already subscribed? Sign In

Save 45% for a limited time.

Get access to all courses and lessons on egghead today.

Autoplay

    Determine if a string is a palindrome

    Basarat Ali SyedBasarat Ali Syed

    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.

    typescriptTypeScript
    Code

    Code

    Become a Member to view code

    You must be a Member to view code

    Access all courses and lessons, track your progress, gain confidence and expertise.

    Become a Member
    and unlock code for this lesson
    Transcript

    Transcript

    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.

    Discuss

    Discuss