Connection Status:
Competition Arena > DirPattern

DirPattern

TC China 08 - 1C · 2008-11-23 · by Mike Mirzayanov

TC China 08 - 1C · 2008-11-23 · by Mike Mirzayanov · String Manipulation
Class Name: DirPattern
Return Type: String
Method Name: matchFiles
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Your home directory contains a list of files. All the filenames have equal length. When you type a command in the form "dir PATTERN", it will show all the filenames that match the specified pattern. A pattern can contain only letters ('a'-'z'), '.' characters, and '?' symbols. Each '?' matches any single character (including '.'), and all other characters match only themselves. For example, the pattern "conte?t.info" matches the filenames "contest.info" and "content.info", but not "contemn.info" or "contests.nfo" (all quotes for clarity only).

You are given a String[] filenames, where each element represents the filename of a single file in your home directory. Return the pattern that will match all the filenames while containing as few '?' symbols as possible.

Constraints

  • filenames will contain between 1 and 50 elements, inclusive.
  • Each element of filenames will contain between 1 and 50 characters, inclusive.
  • All elements of filenames will have equal length.
  • Each element of filenames will contain only lowercase letters ('a'-'z') and '.' characters.
Examples
0)
{"contest.txt", "context.txt"}
Returns: "conte?t.txt"
1)
{"config.sys", "config.inf", "configures"}
Returns: "config????"
2)
{"c.user.mike.programs", "c.user.nike.programs", "c.user.rice.programs"}
Returns: "c.user.?i?e.programs"
3)
{"a", "a", "b", "b"}
Returns: "?"
4)
{"onlyonefile"}
Returns: "onlyonefile"

Submissions are judged against all 91 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DirPattern with a public method string matchFiles(vector<string> filenames) · 91 test cases · 2 s / 256 MB per case

Submitting as anonymous