How to Solve “isSubstitutionCipher” in CodeFights

The Problem:

A ciphertext alphabet is obtained from the plaintext alphabet by means of rearranging some characters. For example "bacdef...xyz" will be a simple ciphertext alphabet where a and b are rearranged.

A substitution cipher is a method of encoding where each letter of the plaintext alphabet is replaced with the corresponding (i.e. having the same index) letter of some ciphertext alphabet.

Given two strings, check whether it is possible to obtain them from each other using some (possibly, different) substitution ciphers.

Example

  • For string1 = "aacb" and string2 = "aabc", the output should be
    isSubstitutionCipher(string1, string2) = true.

    Any ciphertext alphabet that starts with acb... would make this transformation possible.

  • For string1 = "aa" and string2 = "bc", the output should be
    isSubstitutionCipher(string1, string2) = false.

Input/Output

  • [time limit] 4000ms (py)
  • [input] string string1

    A string consisting of lowercase characters.

    Constraints:
    1 ≤ string1.length ≤ 10.

  • [input] string string2

    A string consisting of lowercase characters of the same length as string1.

    Constraints:
    string2.length = strin1.length.

  • [output] boolean

The Solution:
def isSubstitutionCipher(string1, string2):
d = {}
r = {}
for x,y in zip(string1,string2):
if x in d:
if d[x]!=y:
return 0
if y in r:
if r[y]!=x:
return 0
r[y]=x
d[x]=y
return 1

The Explanation:

For each letter in string1, we need to set its substitute, I prefer doing it with dictionary. If it is already set, then it is not a correct substitution cipher. If we set two different letters to the same substitute, it is, again, not a valud subsitution cipher. The way we (I, personally) find it is to create another dictionary to map substitutions to the keys (reverse mapping from string2 to string1).

if two of them is mapped to the same letter, it is invalid again.
If none of these conditions fail, then it is valid, return 1 as True.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s