RecoverWords
TCCC '04 Finals · 2004-02-23 · by lars2520
TCCC '04 Finals · 2004-02-23 · by lars2520 · String Parsing
Problem Statement
Problem Statement
We want to write a program to recover some missing letters from a document. You will be given a sentence, some of whose letters are missing and are represented by '?' (one question mark stands for exactly one missing letter, which cannot be a space). Your goal is to recover the values of all the question marks, given some knowledge about the structure of English.
For the purposes of this problem, we will define a sentence using the following (extremely simplified) grammar:String[] 's. Each element of each of these String[] 's represents one word and is a sequence of one or more lowercase letters.
Your task is to change all of the question marks in sentence into letters such that the sentence matches the given grammar and return the result. If this is not possible (including cases where there are no question marks, but the given sentence doesn't match the grammar), or if there are multiple ways to change some question marks that are consistent with the grammar, return "".
For the purposes of this problem, we will define a sentence using the following (extremely simplified) grammar:
<sentence> ::= <noun phrase> <predicate> [<preposition>] <noun phrase>
<noun phrase> ::= <article> {<adjective>} <noun>
<predicate> ::= <verb> {<adverb>}
Elements in curly braces ('{' and '}') may be present zero or more times, and those in square brackets ('[' and ']') are optional. There are only two <article>'s in English: "a" and "the" (we'll be ignoring "an" in this problem). However, there are thousands of <adjective>'s, <noun>'s, <adverb>'s, <preposition>'s, and <verb>'s. Thus, a small subset of these will be given to you as five Your task is to change all of the question marks in sentence into letters such that the sentence matches the given grammar and return the result. If this is not possible (including cases where there are no question marks, but the given sentence doesn't match the grammar), or if there are multiple ways to change some question marks that are consistent with the grammar, return "".
Notes
- Some words may be serve as multiple parts of speech. This occurs in English with words like "water" which can be both a noun and a verb.
- We are looking to replace the question marks with letters, not understand the semantics of the sentence. Hence, there may be multiple ways to interpret a sentence within the context of the above grammar, which all lead to the question marks being replaced in the same way. See examples 0 and 5.
Constraints
- sentence will contain between 1 and 50 characters, inclusive.
- Each character of sentence will be a lowercase letter ('a'-'z'), a question mark ('?') or a space (' ').
- There will be no double spaces, leading spaces, or trailing spaces in sentence.
- Each of the five input String[]'s will contain between 0 and 50 elements, inclusive.
- Each element of each of the five input String[]'s will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive.
- All complete words without question marks in sentence must be in one of the five input String[]'s (except "a" and "the", which may or may not in the input String[]'s).
Examples
0)
"? ????k b???? f?x ????? ??? ???? dog"
{"fox","fox","dog","dog"}
{"quick", "brown", "lazy"}
{"jumps"}
{}
{}
Returns: "a quick brown fox jumps the lazy dog"
The resulting sentence has the following parts of speech:
1)
"? b?? r?? e????? ???? ??? ?????"
{"rat","boy","field"}
{"big"}
{"ran","eating"}
{"easily"}
{"over"}
Returns: ""
There are two valid interpretations for this sentence: "a big rat eating over the field" "a boy ran easily over the field"
2)
"? b?? r?? e????? ???? ??? ?????"
{"boy","field"}
{"big"}
{"ran","eating"}
{"easily"}
{"over"}
Returns: "a boy ran easily over the field"
Without the rat, there is only one valid interpretation.
3)
"? ??? ??? ??? ??? ??? c?? ??? b?? ??? ??? ??? ???"
{"abc"}
{"bcd"}
{"cde"}
{"def"}
{}
Returns: "a bcd bcd bcd bcd abc cde the bcd bcd bcd bcd abc"
4)
"the horse is"
{"horse","stallion"}
{}
{"is"}
{}
{}
Returns: ""
9)
"??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ???"
{"the"}
{"the"}
{"the"}
{"the"}
{"the"}
Returns: "the the the the the the the the the the the"
There are multiple ways to interpret which part of speech each word is. However, every interpretation results in the same sequence of characters.
Submissions are judged against all 51 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RecoverWords with a public method string recover(string sentence, vector<string> nouns, vector<string> adjectives, vector<string> verbs, vector<string> adverbs, vector<string> prepositions) · 51 test cases · 2 s / 256 MB per case