WordParts
SRM 156 · 2003-07-23 · by LunaticFringe
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.
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).
"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.
"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.
"TOPCODERDOTCOM" "TOMTMODERDOTCOM" Returns: 5
The five strings are "TO", "M", "T", "M", and "ODERDOTCOM".
"HELLO" "HELLOHEHELLOLOHELLO" Returns: 5
Note that the entire original word is considered a valid prefix/suffix.
"DONTFORGETTHEEMPTYCASE" "" Returns: 0
Submissions are judged against all 35 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WordParts with a public method int partCount(string original, string compound) · 35 test cases · 2 s / 256 MB per case