#C2889. Reconstruct the Original Message
Reconstruct the Original Message
Reconstruct the Original Message
You are given a dictionary of valid English words and a corrupted message string. The corrupted message contains lowercase letters and the wildcard character '?' which can represent any single letter. Your task is to determine if there exists a word in the dictionary that matches the pattern of the corrupted message exactly. A match is defined as having the same length as the corrupted message and having identical characters at all positions where the corrupted message has a letter (i.e. not a '?').
If such a word exists, output two lines: the first line should be "YES" and the second line the matched word. If no match is found, simply output "NO".
The matching should be performed in the order in which the dictionary words are provided, and the first valid match should be returned.
Note: If there are multiple valid words (especially in cases where the corrupted message is entirely '?'), returning any one valid match is acceptable.
inputFormat
The input is read from the standard input (stdin) and has the following format:
- The first line contains an integer n, representing the number of words in the dictionary.
- The second line contains n space-separated words.
- The third line contains the corrupted message string, which consists of lowercase letters and '?' wildcards.
outputFormat
Print the result to the standard output (stdout). If a matching word is found in the dictionary, output "YES" on the first line followed by the matched word on the second line. If no matching word exists, output "NO".## sample
3
hello world happy
h?ll?
YES
hello
</p>