Anagrams

Question

• leetcode: Anagrams | LeetCode OJ
• lintcode: (171) Anagrams

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

Example
Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].

Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].
Note
All inputs will be in lower-case

题解1 - 双重for循环(TLE)

题 Two Strings Are Anagrams 的升级版，容易想到的方法为使用双重for循环两两判断字符串数组是否互为变位字符串。但显然此法的时间复杂度较高。还需要 $$O(n)$$ 的数组来记录字符串是否被加入到最终结果中。

Python

class Solution:
    # @param strs: A list of strings
    # @return: A list of strings
    # @return: A list of strings
    def anagrams(self, strs):

        if len(strs) < 2 :
            return strs
        result=[]
        visited=[False]*len(strs)
        for index1,s1 in enumerate(strs):
            hasAnagrams = False
            for index2,s2 in enumerate(strs):
                if index2 > index1 and not visited[index2] and self.isAnagrams(s1,s2):
                    result.append(s2)
                    visited[index2]=True
                    hasAnagrams = True
            if not visited[index1] and hasAnagrams:
                result.append(s1)
        return result

    def isAnagrams(self, str1, str2):
        if  sorted (str1) == sorted(str2):
                return True
        return False

源码分析

1. strs 长度小于等于1时直接返回。
2. 使用与 strs 等长的布尔数组表示其中的字符串是否被添加到最终的返回结果中。
3. 双重循环遍历字符串数组，注意去重即可。
4. 私有方法isAnagrams用于判断两个字符串是否互为变位词。

复杂度分析

私有方法isAnagrams最坏的时间复杂度为 $$O(2L)$$, 其中 $$L$$ 为字符串长度。双重for循环时间复杂度近似为 $$\frac {1}{2} O(n^2)$$, $$n$$ 为给定字符串数组数目。总的时间复杂度近似为 $$O(n^2 L)$$. 使用了Vector String "visited"，空间复杂度可认为是 $$O(n)$$.

题解2 - 排序 + hashmap

在题 Two Strings Are Anagrams 中曾介绍过使用排序和 hashmap 两种方法判断变位词。这里我们将这两种方法同时引入！只不过此时的 hashmap 的 key 为字符串，value 为该字符串在 vector 中出现的次数。两次遍历字符串数组，第一次遍历求得排序后的字符串数量，第二次遍历将排序后相同的字符串取出放入最终结果中。

leetcode 上此题的 signature 已经更新，需要将 anagrams 按组输出，稍微麻烦一点点。

Python lintcode

class Solution:
    # @param strs: A list of strings
    # @return: A list of strings
    # @return: A list of strings
    def anagrams(self, strs):
        strDict={}
        result=[]
        for string in strs:
            if  "".join(sorted(string)) not in strDict.keys():
                strDict["".join(sorted(string))] = 1
            else: 
                strDict["".join(sorted(string))] += 1
        for string in strs:
            if strDict["".join(sorted(string))] >1:
                result.append(string)
        return result

复杂度分析

遍历一次字符串数组，复杂度为 $$O(n)$$, 对单个字符串排序复杂度近似为 $$O(L \log L)$$. 两次遍历字符串数组，故总的时间复杂度近似为 $$O(nL \log L)$$. 使用了哈希表，空间复杂度为 $$O(K)$$, 其中 K 为排序后不同的字符串个数。

Reference

• ^{unordered_map}. unordered_map - C++ Reference ↩

• ^{map-unordered_map}. c++ - Choosing between std::map and std::unordered_map - Stack Overflow ↩

• Anagrams | 九章算法