leetcode之Isomorphic strings

深藏阁楼爱情的钟 2022-12-17 05:20 19阅读 0赞

问题来源：[Isomorphic strings][]  
问题描述：给定两个字符串，判断它俩是否满足同构关系。同构关系表示两个字符串的字符能一一对应，例如title和paper构成同构关系，而foo和bar不构成同构关系。  
该问题属于一个比较简单的题目，利用两个map分别对每个字符串的字符建立映射关系即可判断两个字符串是否满足同构关系（注意：必须要用两个map，可以利用ab和aa来理解）。该问题的有趣之处在于它有多种解决思路，而且相比原始思路会使代码更加简洁。

## 解法一 ##

如果给定字符串的每个字符都是ASCII码（事实也是如此），我们可以不用map来建立映射关系，改用一个长度为128的数组就可以建立映射关系。此时代码如下：

bool isIsomorphic(string s, string t) {
        
            char a[128]={
        0},b[128]={
        0};
            
            for(int i=0;i<s.length();i++)
            {
        
      			//s[i]非第一次出现且之前的赋值和当前不一致
                if(a[s[i]]!=0&&a[s[i]]!=t[i]) return false;
                a[s[i]]=t[i];//s[i]第一次出现
                
                if(b[t[i]]!=0&&b[t[i]]!=s[i]) return false;
                b[t[i]]=s[i];
            }
            
            return true;
        }

## 解法二 ##

另外一种判断同构的思路是将两个字符串都转换到相同的中间态，如果中间态相同则表示是同构的。转换到中间态的基本思路是将字符串转化成计数数组，我们可以记录当前字符是到目前位置出现的第几个不同的字符或者记录当前字符第一次出现的位置，只要转换操作唯一即可。当我们记录当前字符第一次出现的位置时，采用中间态判断同构的代码如下：

bool isIsomorphic(string s, string t) {
        
            vector<int> v(s.length());//中间态数组
            int m[128]={
        0};
            
            for(int i=0;i<s.length();i++)
            {
        
                if(!m[s[i]]) m[s[i]]=i+1;//s[i]第一次出现，记录位置
                v[i]=m[s[i]];
            }
            
            memset(m,0,128*sizeof(int));
            
            for(int i=0;i<t.length();i++)
            {
        
                if(!m[t[i]]) m[t[i]]=i+1;
                if(m[t[i]]!=v[i]) return false;
            }
            
            return true;
        }

## 解法三 ##

上面的解法是先将字符串s转化成中间态，然后再试着将字符串t转化到中间态，在转化的过程中判断是否为同构。事实上，不用先将字符串s转化到中间态，我们可以在单个字符的比较中实时完成到中间态的转化，此时中间态的结果就蕴藏在映射关系中。代码实现如下：

bool isIsomorphic(string s, string t) {
        
            int a[128]={
        0},b[128]={
        0};
            
            for(int i=0;i<s.length();i++)
            {
        
                if(!a[s[i]]) a[s[i]]=i+1;
                if(!b[t[i]]) b[t[i]]=i+1;
                if(a[s[i]]!=b[t[i]]) return false;
            }
            
            return true;
        }

针对上面的解法，我们还可以稍微变换一下思路：当两个字符串在第i个位置不冲突时意味着它们的中间态是相同的，我们可以将其赋相同的值。按照这种思路上述代码可以重构如下：

bool isIsomorphic(string s, string t) {
        
            int a[128]={
        0},b[128]={
        0};
            
            for(int i=0;i<s.length();i++)
            {
        
                if(a[s[i]]!=b[t[i]]) return false;
                a[s[i]]=i+1;
                b[t[i]]=i+1;
            }
            
            return true;
        }

该方法相比原始的解法三少了两个if判断，代码更简洁一点，理解上稍微困难一点。希望大家能从该题目中获得一些启发。

[Isomorphic strings]: https://leetcode.com/problems/isomorphic-strings/