Given two strings s and t, determine if they are isomorphic.(同型的)
Two strings 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.
For example,
Given "egg"
, "add"
, return true.
Given "foo"
, "bar"
, return false.
Given "paper"
, "title"
, return true.
Note: You may assume both s and t have the same length.
bool isIsomorphic(string s, string t)
1、如果两个相同长度的字符串s和t,s中相同的字母能由t中相同位置上的同一个字母来代替,那么它是同构的。比如“add”和“egg”,a由相同位置上的e代替,d由相同位置上的g代替。也就是说要建立对应关系。
2、不能两个不同的字母对应同一个字母,比如“ab”和“ee”就不是同型的,“ee”和“ab”也不是同型的。
3、但是“paper”和“title”是同型的,因为可以e对应l,r对应e。
根据上述规则,我们利用map可以构建出如下代码,一旦出现两个不同的字母试图对应同一个字母,就可以判断它是不同型的。
bool isIsomorphic(string s, string t)
{
map<char,char>m1;
map<char,char>m2;
for(int i=0;i<s.size();i++)//去除"foo"和“bar”这种同一个字母对应两个的情况
{
if(!m1[s[i]])
m1[s[i]]=t[i];
else
{
if(m1[s[i]]!=t[i])
return false;
}
}
for(int i=0;i<t.size();i++)//去除“ab”和“ee”这种两个字母对应同一个的情况
{
if(!m2[t[i]])
m2[t[i]]=s[i];
else
{
if(m2[t[i]]!=s[i])
return false;
}
}
return true;
}
上述代码实测12ms,beats 51.61% 0f cpp submissions。
4、改进
在discuss区看到了这样的代码,也不难理解。
bool isIsomorphic(string s, string t)
{
char map_s[128] = { 0 };
char map_t[128] = { 0 };
int len = s.size();
for (int i = 0; i < len; ++i)
{
if (map_s[s[i]]!=map_t[t[i]]) return false;
map_s[s[i]] = i+1;
map_t[t[i]] = i+1;
}
return true;
}
实测9ms,beats 71.54% of cpp submissions。
还有一大堆人做出来7ms的方法,很好奇……