Challenge 03: Palindrome Permutation

Problem overview

Given a phrase, you are to determine if any permutation of the phrase (ignoring whitespace and punctuation) is a palindrome, which is a phrase that reads the same forwards and backwards. For instance, "taco cat" is an example of a palindrome.

Inspiration

Note, this problem is inspired by an assignment Dr. Scott had as an undergrad, also found in Problem 1.4 from Cracking the Code Interview and Question 30 from Interview Cake.

Input / Output

You will be given a series of phrases from standard input in the following format:

phrase1
phrase2
...

Each line is considered a separate phrase, which can consist of letters, numbers, spaces, and punctuation.

For each input phrase, output a statement saying:

"phrase" is a palindrome permutation

if the input phrase is a palindrome permutation. Otherwise, output:

"phrase" is a not palindrome permutation

Note: To pass all of the gradescripts, you must ignore numbers, spaces, and punctuation prior to (or during) determining if a phrase is a palindrome permutation.

Example

Given the following input:

civic
ivicc
civil
livci

Your program should output the following:

"civic" is a palindrome permutation
"ivicc" is a palindrome permutation
"civil" is not a palindrome permutation
"livci" is not a palindrome permutation

Requirements

You must implement and utilize an is_palindrome(s) function that determines if a string s is a palindrome permutation in O(n) time using a std::unordered_set or std::unordered_map.

---

Rubric

We will grade your submission relative to the rubric below.

+2    Code is well formatted, commented (inc. name, assignment, and overview), with reasonable variable names
+4    Uses an unordered set or unordered map as requested
+24   Test cases successfully solved (~1.7 points each)

Testing your code prior to submission

To faciliate testing, you were previously asked to clone the course Github repository as follows:

git clone https://github.com/semrich/cs302-23.git cs302

For this assignment, update this clone by using the following:

git pull

We'll discuss this in class but note that your program must be named "solution.cpp" and compilable using make. To test your solution against ours, type:

make test

---

Submission

You have previously submitted challenges as cpp files to help you settle in. However, we're going to ask that you submit all your challenges as tar archives. The name doesn't really matter since Canvas will rename it but for your clarity name it something like "challenge3.tar"; your tar file will only contain the solution.cpp file that you wrote for the challenge. This way, hopefully we won't have as much confusion on how to submit, since everything will be tars. Thank you for your patience and flexibility!

Note: Although submission will be faciliated by Canvas, we will compile and test on EECS lab machines!

If you develop your solution elsewhere please make sure it works on the lab computers prior to the deadline

---