Challenge 06: 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: You should ignore numbers, spaces, and punctuation in 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/ds302_19.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

To submit your solution, you must submit a single archive (.zip, .tar, .gz, etc.) on Canvas prior to the deadline.

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

---