一道简单题,用了比较暴力的做法,记录下来只是为了熟悉stl 中map的一些用法。
题意:比较两个字符串s,t是否是同构的(Isomorphic百度翻译),同构的意思只把一个字符串中的某类或者某几类字符替换成另外一类或几类字符后,两个字符串完全一致。
开始天真的以为只有小写字母,于是开了一个26的数组准备存转换关系,结果开心地RE了,基本上什么字符都包括了。。
于是用一个map存字符串s中的字符对应转换关系。例如 s ="aa" ,t = "bc" ,那么遍历第一个的时候 会得到 map<'a' , 'b'>,第二个啊'a'的时候找到应该把'a'对应成'b',但是给的是c所以错了。
开心地以为可以水果,但是把两个字符串交换一下就错了,即s = "bc" ,t = "aa", 第一个得到map<'b','a'>,第二个得到map<'c','a'>,返回true。于是,不能只满足单向对应关系,要双向对应关系都满足才可以。
比较简单的是直接查map的第二操作数,但是具体语法不太清楚又懒。于是开了两个map,一个存s->t,一个存t->s,遍历的时候两个都看一下就好了。
代码如下:
(P.S 今天才发现插入代码这个好东西= =)
1 class Solution { 2 public: 3 bool isIsomorphic(string s, string t) { 4 mapdic1; 5 map dic2; 6 int n = s.length(); 7 for(int i = 0 ; i < n ; i++){ 8 if(dic1.find(s[i]) == dic1.end() && dic2.find(t[i]) == dic2.end()){ 9 dic1[s[i]] = t[i];10 dic2[t[i]] = s[i];11 }else{12 if(dic1.find(s[i]) != dic1.end() && t[i] != (dic1.find(s[i])->second))13 return false;14 if(dic2.find(t[i]) != dic2.end() && s[i] != (dic2.find(t[i])->second))15 return false;16 }17 }18 return true;19 }20 };