IsomorphicWords
SRM 391 · 2008-02-26 · by lovro
Problem Statement
Two words are called isomorphic if the letters in one word can be remapped to get the second word. Remapping a letter means replacing all occurrences of it with another letter. The ordering of the letters remains unchanged. No two letters may map to the same letter, but a letter may map to itself.
For example, the words "abca" and "zbxz" are isomorphic because we can map 'a' to 'z', 'b' to 'b' and 'c' to 'x'.
Given a
Constraints
- words will contain between 2 and 50 elements, inclusive.
- Each element of words will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive.
- All elements of words will have the same length.
- There will be no duplicates in words.
{"abca", "zbxz", "opqr"}
Returns: 1
"abca" and "zbxz" are isomorphic, but none of the two is isomorphic with "opqr".
{"aa", "ab", "bb", "cc", "cd"}
Returns: 4
The four isomorphic pairs are {"aa", "bb"}, {"aa", "cc"}, {"bb", "cc"} and {"ab", "cd"}.
{ "cacccdaabc", "cdcccaddbc", "dcdddbccad", "bdbbbaddcb",
"bdbcadbbdc", "abaadcbbda", "babcdabbac", "cacdbaccad",
"dcddabccad", "cacccbaadb", "bbcdcbcbdd", "bcbadcbbca" }
Returns: 13
{"aab", "abb", "cdd", "ccd"}
Returns: 2
{"aaa", "baa", "cdd", "ddd"}
Returns: 2
Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IsomorphicWords with a public method int countPairs(vector<string> words) · 81 test cases · 2 s / 256 MB per case