I am tasked to write a function that returns whether two strings are substitution ciphers of each other. It is assumed that one isn't given a key. The output is expected to return True or False.
Here is what I have written so far on this (borrowed from a CodeFights question). The idea is to append the counts of each element in the string and add it to the string1count
and string2count
variables. Then, compare the counts at each index, and if they are not equal, we can assume that it is not a valid substitution cipher since each element in the array needs to have the same number of corresponding of characters in order to be a substitution cipher.
def isSubstitutionCipher(string1, string2):
string1count = []
string2count = []
for i in range(0,len(string1)):
string1count.append(string1.count(string1[i]))
for i in range(0,len(string2)):
string2count.append(string2.count(string2[i]))
for i in range(0,len(string1count)):
if string1count.count(string1count[i])!=string2count.count(string1count[i]):
return False
return True
Does anyone else have other proposals on how to solve this very general question / problem statement?
CodePudding user response:
you could try to re-create the subsitution:
def isSubstitutionCipher(string1, string2):
if len(string1) != len(string2):
return False
subst = {}
for c1, c2 in zip(string1, string2):
if c1 in subst:
if c2 != subst[c1]:
return False
else:
if c2 in subst.values():
return False
subst[c1] = c2
return True
for all the characters you have already seen, make sure the substitution matches. for the new ones: store them in the substitution and make sure they are not already a substitution target.
this will return False
at the first character that does not match.
CodePudding user response:
Here is a variation on hiro's excellent answer:
def is_sub(s,t):
if len(s) != len(t):return False
d = dict(zip(s,t))
return t == ''.join(d[c] for c in s)
CodePudding user response:
We can use word patterns to check if one string is the ciphertext of another.
- word pattern: first letter gets the number 0 and the first occurrence of each different letter after that gets the next number.
- advantage is this has O(n) complexity
Code
def isSubstitutionCipher(s1, s2):
def word_pattern(s):
' Generates word pattern of s '
seen, pattern = {}, []
for c in s:
seen.setdefault(c, len(seen))
pattern.append(seen[c])
return pattern
return word_pattern(s1) == word_pattern(s2) # related by ciphertext if same word patterns
Test '
print(isSubstitutionCipher('banana', 'cololo')) # Output: True
print(isSubstitutionCipher('dog', 'cat') # Output: True
print(isSubstitutionCipher('banana', 'cololl') # Output: False