SimilarUserDetection
SRM 689 · 2016-04-01 · by cgy4ever
SRM 689 · 2016-04-01 · by cgy4ever · String Manipulation
Problem Statement
Problem Statement
Each competitor on Topcoder must have a handle.
Sometimes, different people may choose handles that look too similar to each other.
For example, consider the handles "TOPCODER" and "T0PCODER".
These two handles are different: the second character in the first handle is the letter 'O' (big oh), while the second character in the second handle is the digit '0' (zero).
In this problem, all handles are nonempty strings. Each character in a handle must be a letter ('a'-'z', 'A'-'Z') or a digit ('0'-'9'). We will consider two groups of characters that look too similar to each other. The first group are the characters 'O' (big oh) and '0' (zero) mentioned above. The second group are the characters '1' (one), 'l' (lowercase ell), and 'I' (uppercase i).
Strings S and T are called similar if we can change S into T by repeatedly replacing a character by another character from the same group.
You are given theString[] handles.
Return "Similar handles found" if there is at least one pair of similar handles in handles.
Otherwise, return "Similar handles not found".
Note that the quotes are for clarity only and that the return value is case sensitive.
In this problem, all handles are nonempty strings. Each character in a handle must be a letter ('a'-'z', 'A'-'Z') or a digit ('0'-'9'). We will consider two groups of characters that look too similar to each other. The first group are the characters 'O' (big oh) and '0' (zero) mentioned above. The second group are the characters '1' (one), 'l' (lowercase ell), and 'I' (uppercase i).
Strings S and T are called similar if we can change S into T by repeatedly replacing a character by another character from the same group.
You are given the
Constraints
- handles will contain between 2 and 50 elements, inclusive.
- Each element in handles will contain between 1 and 50 characters, inclusive.
- Each character in handles will be '0'-'9', 'a'-'z' or 'A'-'Z'.
Examples
0)
{"top", "coder", "TOPCODER", "TOPC0DER"}
Returns: "Similar handles found"
"TOPCODER" and "TOPC0DER" are similar.
1)
{"Topcoder", "topcoder", "t0pcoder", "topcOder"}
Returns: "Similar handles not found"
No two of these handles are similar. Note that case matters: the letter 'o' (lowercase oh) is not in the group with 'O' and '0'.
2)
{"same", "same", "same", "different"}
Returns: "Similar handles found"
Any two identical strings are similar.
3)
{"0123", "0I23", "0l23", "O123", "OI23", "Ol23"}
Returns: "Similar handles found"
These six handles are all similar to each other.
4)
{"i23", "123", "456", "789", "000", "o", "O"}
Returns: "Similar handles not found"
Submissions are judged against all 111 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SimilarUserDetection with a public method string haveSimilar(vector<string> handles) · 111 test cases · 2 s / 256 MB per case