TopCoder problem "WordParts" used in SRM 156 (Division II Level Three)



Problem Statement

    

Given a base word, original, and a compound word, compound, decide if the compound word is valid. A compound word is valid if and only if it is comprised solely of a concatenation of prefixes and/or suffixes of original. That is, if the compound word can be partitioned into N parts, such that each part is equal to either a prefix or a suffix of original, then it is valid. If the word is invalid, return -1. Otherwise, return the minimum value of N for which this is possible.

 

Definition

    
Class:WordParts
Method:partCount
Parameters:String, String
Returns:int
Method signature:int partCount(String original, String compound)
(be sure your method is public)
    
 

Notes

-The entire base word original is considered a valid prefix/suffix of itself. See example 3.
 

Constraints

-original will contain between 1 and 50 characters, inclusive.
-original will consist only of uppercase letters (A-Z).
-compound will contain between 0 and 50 characters, inclusive.
-compound will consist only of uppercase letters (A-Z).
 

Examples

0)
    
"ANTIDISESTABLISHMENTARIANISM"
"ANTIDISIANISMISM"
Returns: 3

"ANTIDISIANISMISM" can be split into "ANTIDIS", "IANISM", and "ISM", all of which are substrings from the beginning or end of the base word.

1)
    
"ANTIDISESTABLISHMENTARIANISM"
"ESTABLISHMENT"
Returns: -1

While "ESTABLISHMENT" is contained in "ANTIDISESTABLISHMENTARIANISM", it neither starts at the beginning nor ends at the end of that string. Furthermore, "ESTABLISHMENT" cannot be broken into any number of parts which satisfy this rule.

2)
    
"TOPCODERDOTCOM"
"TOMTMODERDOTCOM"
Returns: 5
The five strings are "TO", "M", "T", "M", and "ODERDOTCOM".
3)
    
"HELLO"
"HELLOHEHELLOLOHELLO"
Returns: 5

Note that the entire original word is considered a valid prefix/suffix.

4)
    
"DONTFORGETTHEEMPTYCASE"
""
Returns: 0
5)
    
"BAAABA"
"BAAABAAA"
Returns: 2
6)
    
"ABBBAABABBBAABBABBABABBABAABBAABBBBBABBABABBABAABB"
"BBBAABABBBAABBABBABABBABAABBAABBBBBABBABABBABAABAA"
Returns: 17

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4585&pm=1361

Writer:

LunaticFringe

Testers:

lbackstrom , brett1479

Problem categories:

Dynamic Programming