Connection Status:
Competition Arena > grafixCorrupt

grafixCorrupt

SRM 211 · 2004-09-14 · by Eeyore

SRM 211 · 2004-09-14 · by Eeyore · Simple Search, Iteration
Class Name: grafixCorrupt
Return Type: int
Method Name: selectWord
Arg Types: (vector<string>, string)
Problem Statement

Problem Statement

In the grafix file format, a bitmap is encoded as a sequence of lowercase alphabetic words. All of these words are drawn from a dictionary that has been built specially for the bitmap by a compression algorithm. Each word in the dictionary has the same length.

It can occur that words in a grafix file are corrupted by poor transmission or storage media. In such cases, grafix attempts to reconstruct the original file by matching each corrupted word to a dictionary word that contains one or more of the same characters at the same positions.

You are given a String[], dictionary, containing every word in a grafix file's dictionary, and a String, candidate, which is a possibly corrupted word in that file. If there is no dictionary word that has at least one character in the same position as candidate, then return the int value -1. Otherwise, return the zero-based index of the dictionary word that has the greatest number of characters at the same positions as candidate. In the event of a tie, favor the lowest index.

Constraints

  • dictionary contains between 1 and 50 elements, inclusive
  • candidate is between 1 and 20 characters long, inclusive
  • each element of dictionary has the same length as candidate
  • only the characters 'a' to 'z' are permitted in candidate and dictionary
Examples
0)
{"cat", "cab", "lab"}
"dab"
Returns: 1

The word "dab" has two letters in the same position as both "cab" and "lab", but "cab" comes first.

1)
{"cat", "cab", "lab"}
"lag"
Returns: 2

Here, "lab" is the best fit.

2)
{"cat", "cab", "lab"}
"dog"
Returns: -1
3)
{"bobble", "bubble", "rubble", "hubble", "supple"}
"dimple"
Returns: 4
4)
{"double", "bobble", "bubble", "rubble", "hubble", "supple"}
"dimple"
Returns: 0
50)
{"cat", "cab", "lab"}
"bic"
Returns: -1

The word "bic" contains a 'c' and a 'b', but neither character is at the same position in any dictionary word.

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

Coding Area

Language: C++17 · define a public class grafixCorrupt with a public method int selectWord(vector<string> dictionary, string candidate) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous