美文网首页lintcode
638. 字符同构

638. 字符同构

作者: 和蔼的zhxing | 来源:发表于2018-01-04 20:16 被阅读17次

给定两个字符串 s 和 t ,确定它们是否是同构的。
两个字符串是同构的如果 s 中的字符可以被替换得到 t。
所有出现的字符必须用另一个字符代替,同时保留字符串的顺序。 没有两个字符可以映射到同一个字符,但一个字符可以映射到自己。

样例
给出 s = "egg", t= "add", 返回 true。
给出 s = "foo", t= "bar", 返回 false。
给出 s = "paper", t= "title", 返回 true。

哈希映射

用两个哈希表分别来存放两个字符串每个字符出现的次数,存放的过程中检查同一位置(字符串同一位置)的字符在两个哈希表中的出现的次数是否相等,如果不想等,则肯定不能同构,如果所有的都满足相等,则可同构。
这个算法的思路不是我想出来的,见这里,理解了好一会儿才明白。

因为是一一映射,所以这样遍历过来的话,两个哈希表的值增加,那么肯定最后得到的对应位置的值肯定是相等的,比如说建立的哈希表是ss<char,int>tt<char,int>,如果是s中的B和t中的C映射,那么每一步遍历中都应该有ss[B]=tt[C],因为s中出现一次B,t中也出现一次C,而且必须是立即出现(遍历到这一步就出现)。
画个图看一下:

算法示意
如果不对应映射的话可以改一个字母重复上面的过程,会更理解一些。

用map直接来做。

bool isIsomorphic(string s, string t)
    {
        int sz=s.size();
        map<char,int> ss;
        map<char,int> tt;
        for(int i=0;i<sz;i++)
        {
            ss[s[i]]++;
            tt[t[i]]++;
            if(ss[s[i]]!=tt[t[i]])
            return false;
        }
        return true;
        
    }

用数组也可以

因为字母也是存储的ascii码的,所以也可用数组来做,ascii码一共256个,可以用256的数组来做,写法基本是完全相同的,只是数组可以全部初始化为0,而map的话遇见了才添加,所以只有细微差别:

  bool isIsomorphic(string s, string t) {
        int m1[256] = {0}, m2[256] = {0}, n = s.size();
        for (int i = 0; i < n; i++) {
            if (m1[s[i]] != m2[t[i]]) return false;
            m1[s[i]] += 1;
            m2[t[i]] += 1;
        }
        return true;
    }

这个题难的是思想,代码写起来倒是不难。重视!!

相关文章

  • 638. 字符同构

    给定两个字符串 s 和 t ,确定它们是否是同构的。两个字符串是同构的如果 s 中的字符可以被替换得到 t。所有出...

  • 2019-11-15 同构字符串

    给定两个字符串 s 和 t,判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构...

  • 同构字符串

    给定两个字符串 s 和 t,判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构...

  • T205、同构的字符串

    给定两个字符串 s 和 t,判断它们是否是同构的。如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的...

  • 49同构字符串

    给定两个字符串 s 和 t,判断它们是否是同构的。如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的...

  • 同构字符串

    题目 难度级别:简单 给定两个字符串 s 和 t,判断它们是否是同构的。 如果 s 中的字符可以被替换得到 t ,...

  • 字符串的最小表示法

    字符串的循环同构:设S=bcad,且S’是S的循环同构的串。S’可以是bcad或者cadb,adbc,dbca。而...

  • 205. 同构字符串(Python)

    题目 难度:★★☆☆☆类型:字符串 给定两个字符串 s 和 t,判断它们是否是同构的。 如果 s 中的字符可以被替...

  • 8.23刷题题解代码

    202 快乐数 205 同构字符串 思路总结:第1种,把字符串转换成了数组,通过比较数组是否相等来判断字符串是否同...

  • 数据结构与算法-同构字符串205(java)

    tags: 字符串categories: 数据结构与算法 题目:给定两个字符串 s 和 t,判断它们是否是同构的。...

网友评论

    本文标题:638. 字符同构

    本文链接:https://www.haomeiwen.com/subject/obldnxtx.html