TopCoder problem "PalindromePhrases" used in SRM 439 (Division I Level Two)



Problem Statement

    One of your friends has given you several words and asked you how many palindromic phrases you can compose with those words. To save yourself some time, you've decided to write a program to answer this question. In this problem, a word is defined as a non-empty sequence of lowercase letters ('a'-'z'). A phrase is a non-empty sequence of words, where each pair of consecutive words is separated with exactly one space character. A phrase is palindromic if it reads the same forward and backward, ignoring space characters.



You are given a String[] words. Return the number of different palindromic phrases that can be composed with the given words. Each word in words can be used at most once within each phrase. Two phrases are considered different if they are different strings, even if they read the same when ignoring spaces (for example, "a ba" and "ab a" are different phrases).
 

Definition

    
Class:PalindromePhrases
Method:getAmount
Parameters:String[]
Returns:long
Method signature:long getAmount(String[] words)
(be sure your method is public)
    
 

Constraints

-words will contain between 1 and 13 elements, inclusive.
-Each element of words will contain between 1 and 13 lowercase letters ('a'-'z'), inclusive.
-All elements of words will be distinct.
 

Examples

0)
    
{"a","ba"}
Returns: 2
You can construct two palindromic phrases "a" and "a ba".
1)
    
{"ab","bcd","efg"}
Returns: 0
No palindromic phrases can be built.
2)
    
{"a", "bba", "abb"}
Returns: 7
Here we have 7 palindromic phrases: "a", "a bba", "abb a", "abb bba", "bba abb", "abb a bba", "bba a abb". Note that even though "a bba" and "abb a" represent the same palindrome, they differ as strings, so we count both of them.
3)
    
{"aabccc", "ccbbca", "a", "acaabb", "aaa", "aab", "c", "babb", "aacaa", "b"}
Returns: 47

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10382

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13747&pm=10382

Writer:

it4.kp

Testers:

PabloGilberto , Andrew_Lazarev , ivan_metelsky

Problem categories:

Dynamic Programming