题目描述
给定两个字符串,检查它们是否是结构相似的。
对于结构相似的定义如下
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.
两个字符串的每个字符之间存在某种唯一确定的映射关系,且必须是一一对应,即不能有两个不同的字符对应同一个字符。同时该映射可以是自己到自己。
My Solution
我的直接想法就是直接建立两组映射关系,即从s->t 和 t->s。然后去check是否一一对应。代码如下
from collections import defaultdict
class Solution1(object):
def isIsomorphic(self, s, t):
if len(s)!=len(t):
return False
else:
mapp=defaultdict(list)
rev_mapp=defaultdict(list)
for i,j in zip(s,t):
if j not in mapp[i]:
mapp[i].append(j)
if i not in rev_mapp[j]:
rev_mapp[j].append(i)
for k,v in mapp.items():
if len(v)>1:
return False
for k,v in rev_mapp.items():
if len(v)>1:
return False
return True
Another Solution
对于字符串s和t,都去建立一个转换字符,类似于数字编码的过程。然后去比较两个字符串的编码是否相同。转换字符的过程通过transformString
函数来实现。代码如下
class Solution2(object):
def transformString(self,s):
idx_mapping={}
new_str=[]
for i,item in enumerate(s):
if item not in idx_mapping:
idx_mapping[item]=i
new_str.append(str(idx_mapping[item]))
return ' '.join(new_str)
def isIsomorphic(self,s,t):
return self.transformString(s)==self.transformString(t)