242. 有效的字母异位词 242. Valid Anagram 《编程珠玑》读书笔记

[Shellbye]

不得不承认，我对读算法书还是有些抵触或者说是畏惧的，或许一切都始于大一时买了又退了的那本英文版的《Introduction to Algorithms》（《算法导论》）。忘了是啥时候，老婆给买了本《编程珠玑》，反正是好长时间了，我却一直没勇气读。最近为了某些原因，终于鼓起勇气断断续续开始读了。有意思的是，每次读，其实都有收获，那么这次我就把它记录下来，算是一个开头。

书中第二章的2.4 排序讲到了一个叫变位词的概念，也就是leetcode上的字母异位词：字母相同，但排列不同的字符串。顺着这个概念，我在leetcode上找到了如下一个比较简单的题

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 示例 1:

输入: s = "anagram", t = "nagaram" 输出: true

示例 2:

输入: s = "rat", t = "car" 输出: false

说明:

你可以假设字符串只包含小写字母。

初步分析

因为我刚看完《编程珠玑》相关章节，所以就用到了书里提到的一个思路：把字母对应成数字进行排序，那么排序结果一样的则原字符串就是字母异位词，代码如下：

import java.util.Arrays;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        byte[] sb = s.getBytes();
        byte[] tb = t.getBytes();
        Arrays.sort(sb);
        Arrays.sort(tb);
        return Arrays.equals(sb, tb);
    }
}

更快的方法

上面的方法虽然是一个正确的解答，但是需要先排序，所以时间复杂度就明显高了，应该是O(nlogn)。还有一种其实比较直观的思路，就是记录在第一个字符串中出现过的字母的次数，看是不是在第二个里面也出现了相同的次数，如果没有，那么就不是字母异位词。具体实现如下

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] sc = s.toCharArray();
        char[] tc = t.toCharArray();
        char[] mp = new char[27];
        for (int i = 0; i < sc.length; i++) {
            mp[sc[i]-'a']++;
            mp[tc[i]-'a']--;
        }
        for (int i = 0; i < mp.length; i++) {
            if (mp[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

这个因为没有进行排序，只是一个简单的循环而已，所以时间复杂度就降到了O(n)。