2023-04-13：给定一个字符串数组strs，其中每个字符串都是小写字母组成的，如果i < j，并且strs[i]和strs

福大大架构师每日一题

发布于 2023-06-08 16:29:04

2310

发布于 2023-06-08 16:29:04

文章被收录于专栏：福大大架构师每日一题

2023-04-13：给定一个字符串数组strs，其中每个字符串都是小写字母组成的，

如果i < j，并且strs[i]和strs[j]所有的字符随意去排列能组成回文串，

那么说(i,j)叫做一个互补对(complementary)。

求strs中有多少个互补对。

strs长度 <= 3 * 10^5，

单个字符串长度 <= 10^5，

strs里所有字符串总长度 <= 10^6。

来自亚马逊。

答案2023-04-13：

这道题有两种算法：

### 算法一

该算法使用暴力方法，时间复杂度为 O(N^2*M)，其中，N 表示字符串数组的长度，M 表示单个字符串的平均长度。空间复杂度为 O(1)。

算法过程如下：

1. 遍历每对字符串(i,j)，其中 i<j。

2. 判断字符串 strs[i] 和 strs[j] 是否可以组成回文串。

3. 如果可以组成回文串，则互补对数加一。

判断字符串是否可以组成回文串的过程如下：

1. 统计字符串中每个字符出现的次数。

2. 如果某个字符出现了奇数次，则不能组成回文串，返回 false。

3. 如果所有字符都出现了偶数次，或只有一个字符出现了奇数次，则可以组成回文串，返回 true。

### 算法二

基于状态压缩的哈希表方法，通常也称为“状态压缩 + 哈希表”算法。该算法可以有效地避免枚举所有可能的字符串排列组合，从而实现了较优的时间复杂度。

该算法时间复杂度为 O(N*M)，其中，N 表示字符串数组的长度，M 表示单个字符串的平均长度。空间复杂度为 O(N)。其中，空间复杂度主要来自于 status 哈希表的存储。

算法过程如下：

1. 初始化 hash map status，用于统计每种状态下的字符串数量。

2. 遍历每个字符串 str。

3. 计算字符串 str 的状态 cur，即将字符串中每个字符对应的二进制位取反后进行异或操作得到的结果。

4. 将 status 中 cur 对应的字符串数量加到答案 ans 上。

5. 遍历每个字符 ch，将 cur 取反后在第 ch 位上的值，即 (cur ^ (1 << ch))，对应的字符串数量加到答案 ans 上。

6. 将 cur 加入 status 中。

计算状态 cur 的过程如下：

1. 初始化变量 cur 为 0。

2. 遍历字符串 str 中的每个字符 ch。

3. 将 ch 对应的二进制位取反，即 (1 << (ch as usize - 'a' as usize))。

4. 将上一步得到的结果与 cur 进行异或操作。

补充说明：该算法的思路是通过统计字符串中每个字符出现的奇偶次数，将字符串转化成一个状态值。如果两个字符串可以组成互补对，那么它们的状态值必须相同或者只有一位不同。因此，我们遍历所有字符串，用 hash map 统计每种状态值的出现次数，并统计能够产生互补对的字符串数量。

### rust完整代码如下：

use std::collections::HashMap;

// 暴力方法
// 时间复杂度O(N^2 * M)，N字符串长，M字符串平均长度
fn num1(strs: &[String]) -> usize {
    let mut ans = 0;
    for i in 0..strs.len() {
        for j in (i + 1)..strs.len() {
            if complementary(&strs[i], &strs[j]) {
                ans += 1;
            }
        }
    }
    ans
}

fn complementary(a: &str, b: &str) -> bool {
    let mut cnt: [usize; 26] = [0; 26];
    for ch in a.chars() {
        let idx = ch as usize - 'a' as usize;
        cnt[idx] += 1;
    }
    for ch in b.chars() {
        let idx = ch as usize - 'a' as usize;
        cnt[idx] += 1;
    }
    let odd = cnt.iter().filter(|&&num| num % 2 != 0).count();
    odd < 2
}

// 正式方法
// O(N*M)，N字符串长，M字符串平均长度
// 时间复杂度O(N) + O(M)，一共有多少个字符串N，一共有多少字符M
fn num2(strs: &[String]) -> usize {
    let mut status: HashMap<usize, usize> = HashMap::new();
    let mut ans = 0;
    for str in strs {
        let cur = str
            .chars()
            .fold(0, |acc, ch| acc ^ (1 << (ch as usize - 'a' as usize)));
        ans += status.get(&cur).unwrap_or(&0);
        for i in 0..26 {
            ans += status.get(&(cur ^ (1 << i))).unwrap_or(&0);
        }
        status.entry(cur).and_modify(|cnt| *cnt += 1).or_insert(1);
    }
    ans
}

// 为了验证
fn random_string_array(n: usize, m: usize, r: usize) -> Vec<String> {
    let mut ans = vec![];
    for _ in 0..n {
        let len = rand::random::<usize>() % m + 1;
        let mut str = String::new();
        for _ in 0..len {
            let ch = rand::random::<usize>() % r + 'a' as usize;
            str.push(ch as u8 as char);
        }
        ans.push(str);
    }
    ans
}

fn main() {
    const N: usize = 100;
    const M: usize = 20;
    const R: usize = 5;
    const TEST_TIME: usize = 5000;
    println!("测试开始");
    for _ in 0..TEST_TIME {
        let n = rand::random::<usize>() % N + 1;
        let strs = random_string_array(n, M, R);
        let ans1 = num1(&strs);
        let ans2 = num2(&strs);
        if ans1 != ans2 {
            println!("出错了!");
        }
    }
    println!("测试结束");
}