算法练习：回文构词法（Anagram）

[ShannonChenCHN]

题目 1 判断 Anagram

描述

Given two strings s and t, write a function to determine if t is an anagram of s. For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false.

Note:

You may assume the string contains only lowercase alphabets.

分析

方案1：为s和t分别建立一个HashMap，统计每个字母出现的次数，比较两个HashMap是否相等。时间复杂度O(n)，空间复杂度O(n)，n为字符串长度。

方案2：题目中的字符串只包含小写的字母，意味着只有从a-z的26个字母，于是我们可以为s和t开一个长度为26的整数数组来代替哈希表，此时额外空间为固定长度的两个数组，因此为O(1)。

#define ALPHABET_SIZE  26

BOOL isAnagram(NSString *s, NSString *t) {
    if (s.length != t.length) {
        return NO;
    }

    int map[ALPHABET_SIZE] = {}; // C 数组必须要初始化，才能保证所有元素初始值为 0
    for (int i = 0; i < s.length; i++) {
        int indexForS = [s characterAtIndex:i] - 'a';
        map[indexForS] = map[indexForS] + 1;

        int indexForT = [t characterAtIndex:i] - 'a';
        map[indexForT] = map[indexForT] - 1;
    }

    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (map[i] != 0) {
            return NO;
        }
    }

    return YES;
}

参考

• 算法珠玑

[ShannonChenCHN]

题目2 查找 Anagram

描述

Given an array of strings, return all groups of strings that are anagrams.

Note:

All inputs will be in lower-case.

参考：

• 算法珠玑