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

题目

给定两个字符串 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;
    }