LeetCode 49.字母异位词分组

LeetCode 49.字母异位词分组

题面：

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词：【字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次】

解析：

• 对于这道题，分类是我们的目标，最根本的点在于“字符出现频率”会成为分类的标准。也就是讲我们如何根据每个字符串中字符出现的频率赋予其一个唯一标准OID/Key（只取决于该字符串中字符出现的频率），相同OID/Key的字符串分到一组即可。难点就在于怎么把一个字符串“ 字符出现频率 ”变为可以进行比较（==?）的 OID/Key。

• 再底层一些就是 Hash 思维，针对于我们平时说的杂凑函数（Hash）：字符串a,b，若a == b --> hash(a) = hash(b)，反之，很难碰撞出 a≠ b and hash(a) = hash(b)。这是一般的杂凑函数，他是根据字符串是否完全相等为杂凑值标准的，针对于这道题目，字符串中的字符出现的频率是其标准。

  1. 排序的底层逻辑就是，如若我完成了排序，就将“字符出现频率”的分类标准转化为了“字符串相等” ；
  2. 数组标记则是直接统计“字符出现频率”，以频率数组作为 OID/Key；
  3. 素数乘积的方法，其利用了素数乘法会造成结果的唯一性，也就是找到了一种实现方法，将字符串中的字符出现频率进行唯一性的转化。isPrime(a) and isPrime(b)... (a * b *b)的结果不能由其他方式的乘积表示出来，即素因子分解唯一性。其本质还是数组标记法，唯一的不同就是数组标记法我们需要想办法把“字符出现频率”转化为可以比较的对象了。 2方法与3方法底层逻辑都是一样的，前者需要先完成统计，此后再进行以特殊字符串符号的拼接，例如"#"，而后者由于素因子分解的唯一性，可以直接进行即时性频率转化。

• 最终目的都是达到了：相同字符频率会产生相同的OID，不同字符频率的字符串不会产生相同的OID。

复杂度

时间复杂度：\(O(N + MlogM)/O(N + M + 26)/O(N + M)\)

Code

// C++
// 数组标记
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string, vector<string>> temp;
        for (string str : strs)
        {
            uint8_t count[26] = {0};
            for (char c : str)
            {
                count[c - 'a']++;
            }
            string OID = "";
            for (uint8_t i : count)
            {
                OID += char(i);
                OID += "#";
            }
            temp[OID].push_back(str);
        }
        vector<vector<string>> ans;
        for (auto& pair :temp)
        {
            ans.push_back(pair.second);
        }
        return ans;
    }
};

# Python
# 排序
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)

        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)
        return list(mp.values())

// Rust
// 素因子乘积
use std::collections::HashMap;

impl Solution {
    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
        let primes: [u64; 26] = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103];
        
        let mut groups: HashMap<u64, Vec<String>> = HashMap::new();
        
        for s in strs {
            let mut key: u64 = 1;
            
            for ch in s.chars() {
                let index = (ch as u8 - b'a') as usize;
                key = key.wrapping_mul(primes[index]);
            }
            
            groups.entry(key).or_insert_with(Vec::new).push(s);
        }
        
        groups.into_values().collect()
    }
}

• 注：由于Python排序的底层是由C来完成优化的，这比纯Python的数组统计可能要快上不少，因为C++实现的方法需要进行循环以及类型对象的转化，因此数组统计的方法在C/C++中可能会效果更加显著。