这是悦乐书的第198次更新,第205篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第61题(顺位题号是242)。给定两个字符串s和t,写一个函数来确定t是否是s的anagram。例如:

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

输入:s =“anagram”,t =“nagaram”

输出:true

输入:s =“rat”,t =“car”

输出:false

注意:您可以假设该字符串仅包含小写字母。

跟进:如果输入包含unicode字符怎么办? 您如何使您的解决方案适应这种情况?


本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

关于题目中anagram的意思,结合给出的两个示例,大意就是两字符串使用的小写字母一样,但是每个字母所处的位置不是全都一样。此解法是将两字符串s、t转换为字符数组,然后将数组排序,最后比较两数组的元素是否相等,这里借助了工具类Arrays。

此解法的时间复杂度是O(nlog(n)),空间复杂度是O(n)。

public boolean isAnagram(String s, String t) {
    if (s == null || t == null || s.length() != t.length()) {
        return false;
    }
    char[] ch = s.toCharArray();
    char[] ch2 = t.toCharArray();
    Arrays.sort(ch);
    Arrays.sort(ch2);
    return Arrays.equals(ch, ch2);
}


03 第二种解法

题目限制了只有英文小写字母,我们可以定义一个长度只有26的整数数组,对字符串进行遍历,以当前字符减去字符a所表示的整数为索引,找到对应元素,字符串s所在的字符进行自增,字符串t所在的字符进行自减,然后判断数组中的元素,只要任一元素不等于0,则说明s和t不满足anagram的条件。

此解法时间复杂度是O(n),空间复杂度是O(1)。

public boolean isAnagram2(String s, String t) {
    if (s == null || t == null || s.length() != t.length()) {
        return false;
    }
    int[] arr = new int[26];
    for (int i=0; i<s.length(); i++) {
        arr[s.charAt(i)-'a']++;
        arr[t.charAt(i)-'a']--;
    }
    for(int num : arr) {
        if (num != 0) {
            return false;
        }
    }
    return true;
}


04 第三种解法

使用HashMap,key为字符串的单个字符,value为此字符出现的次数,这里借助HashMap的getOrDefault方法来实现,如果存在该key,返回对应的value,否则返回默认值。

先将字符串s的每个字符存入HashMap中,然后遍历字符串字符串t,依次获取每一个字符,如果当前字符不在HashMap中存在,直接返回false,然后将字符存进HashMap中,value值减1,如果当前字符的出现次数为0了,将其remove掉,最后判断HashMap是否为空。

此解法因为用到了map.containsKey()方法,所以时间复杂度最好的情况是O(n),最坏的情况是O(n^2),空间复杂度是O(n)。

public boolean isAnagram3(String s, String t) {
    if (s == null || t == null || s.length() != t.length()) {
        return false;
    }
    HashMap<Character,Integer> map = new HashMap<Character,Integer>();
    for (int i=0; i<s.length(); i++) {
        char ch = s.charAt(i);
        map.put(ch, map.getOrDefault(ch, 0)+1);
    }
    for (int j=0; j<t.length(); j++) {
        char ch = t.charAt(j);
        if (!map.containsKey(ch)) {
            return false;
        }
        map.put(ch, map.get(ch)-1);
        if (map.get(ch) == 0) {
            map.remove(ch);
        }
    }
    return map.isEmpty();
}

此解法是可以应对那些带有unicode字符的字符串,当然也可以使用像第二种解法的那样,使用数组,但是数组容量要扩大到256,其他的思路都是一样的。

05 小结

算法专题目前已连续日更超过一个月,算法题文章61+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄