Isomorphic Strings in Python

user_13232323 0
Viewed 283

Here's my code:

def isIso(x,y):
  if len(x) != len(y):
    return False
  for i in range(len(x)):
    count = 0
    if x.count(x[i]) != y.count(y[i]):
      return False
  return True

Why do all solutions for this question online involve mapping or dictionaries? I'm wondering why everyone seems to be overcomplicating the solution to this problem. Is it a time complexity thing? The time complexity of this is n which is not ideal - are people using maps/dictionaries because of a better time complexity?

isomorphism time-complexity algorithm python string
3 Answers

The time complexity of this is n which is not ideal

No! Your time complexity is not on the order of n. It is on the order of n2.

str.count must loop through the entire string every time, n operations. And you call it n times. So the result is n*n = n2 complexity, much much worse than if you store the counts in a dictionary and look them up.

The simplest implementation in Python that would be on the order of n time is:

from collections import Counter
def is_isomoprhic(x, y):
    xc, yc = Counter(x), Counter(y)
    return all(xc[a] == xc[b] for a, b in zip(x, y))
user_5656350

Simplest solution you will ever find --- Thank you!!!

len(set(zip(list(s), list(s1)))) == len(set(s))
user_62582720

Using maketrans and translate.

def is_isometric(x: str, y: str) -> bool:
    trans = str.maketrans(x, y)
    return x.translate(trans) == y
user_300380
Related