欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LC205 - 同构字符串 - 桶排序/计数排序

程序员文章站 2022-05-12 15:53:49
...

题目

给定两个字符串 s 和 t,判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ,那么这两个字符串是同构的。

输入: s = "egg", t = "add"
输出: true
输入: s = "foo", t = "bar"
输出: false

思路

  • 维护两个数组
  • 由于ASCII 码使用指定的7 位或8 位二进制数组合来表示128 或256种可能的字符。大小写字符一共是256个,所以要维持长度为256的数组
  • index为s,t中的字符,数组存储的value是该字符出现的次数,依次遍历字符串时,如果字符串出现的次数不等同,则非同构。

知识点

计数排序包含桶排序的算法思想。

https://www.bilibili.com/video/BV1Wb41157ed?from=search&seid=8220052170275915157

计数排序适用于量特别大,但是数据范围小的情况(员工年龄排序,快速得知高考名次)

创建count数组用来计数,数组的长度是可以取值的长度。比如0-60岁,数组长度就设为61,数组下标index即为0-60,读取到某个数则下标+1,比如有3个0岁,则下标为count[0]的value值为3

  • 空间复杂度为O(n+k), 原数组长度为n,需要分配一个长度为n的数组作为返回结果值, 除此以外需要分配一个长度为k的数组记录原数组每个数分别出现多少次。
  • 时间复杂度,遍历原数组一次,n次,往新数组里写数据,n次,遍历count数组k次,所以时间复杂度为O(n+k)≈O(n)

代码

public boolean isIsomorphic(String s, String t) {
        
        if(s.length() != t.length()){
            return false;
        }

        //记录每个字符出现的次数
        int length = s.length();
        int[] preIndexS = new int[128];//计数排序思想
        int[] preIndexT = new int[128];
        for(int i = 0; i < length; i++){
            char sc = s.charAt(i);
            char tc = t.charAt(i);
            if(preIndexS[sc]!=preIndexT[tc]){
                return false;//当出现的次数不同时
            }
            preIndexS[sc] = i + 1;//出现了一次, 则+1
            preIndexT[tc] = i + 1;
        }

        return true;
    }
相关标签: 每日刷题