PalindromePhrases
SRM 439 · 2009-04-30 · by it4.kp
SRM 439 · 2009-04-30 · by it4.kp · Dynamic Programming
Problem Statement
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 aString[] 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).
You are given a
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
4)
{"a",
"aa",
"aaa",
"aaaa",
"aaaaa",
"aaaaaa",
"aaaaaaa",
"aaaaaaaa",
"aaaaaaaaa",
"aaaaaaaaaa",
"aaaaaaaaaaa",
"aaaaaaaaaaaa",
"aaaaaaaaaaaaa"}
Returns: 16926797485
Submissions are judged against all 48 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PalindromePhrases with a public method long long getAmount(vector<string> words) · 48 test cases · 2 s / 256 MB per case