algorithm-class/算法周更班/class_2022_11_3_week/Code01_ComplementaryPairsInStringArray.java

package class_2022_11_3_week;

import java.util.HashMap;

// 来自亚马逊
// 给定一个字符串数组strs，其中每个字符串都是小写字母组成的
// 如果i < j，并且strs[i]和strs[j]所有的字符随意去排列能组成回文串
// 那么说(i,j)叫做一个互补对(complementary)
// 求strs中有多少个互补对
// strs长度 <= 3 * 10^5
// 单个字符串长度 <= 10^5
// strs里所有字符串总长度 <= 10^6
public class Code01_ComplementaryPairsInStringArray {

	// 暴力方法
	// 为了测试
	public static int num1(String[] strs) {
		int ans = 0;
		for (int i = 0; i < strs.length; i++) {
			for (int j = i + 1; j < strs.length; j++) {
				if (complementary(strs[i], strs[j])) {
					ans++;
				}
			}
		}
		return ans;
	}

	public static boolean complementary(String a, String b) {
		int[] cnt = new int[26];
		for (int i = 0; i < a.length(); i++) {
			cnt[a.charAt(i) - 'a']++;
		}
		for (int i = 0; i < b.length(); i++) {
			cnt[b.charAt(i) - 'a']++;
		}
		int odd = 0;
		for (int num : cnt) {
			if ((num & 1) != 0) {
				odd++;
			}
		}
		return odd < 2;
	}

	// 正式方法
	// O(N*M)，N字符串长，M字符串平均长度
	// 时间复杂度O(N) + O(M)，一共有多少个字符串N，一共有多少字符M
	public static int num2(String[] strs) {
		// key : 某一种状态(int类型，状态)
		// z..d c b a
		// 3 2 1 0
		// 1 0 1 1
		// value : 这样状态的字符串，有几个
		HashMap<Integer, Integer> status = new HashMap<>();
		int ans = 0;
		for (String str : strs) {
			// 当前str这个字符串
			// 它自己的状态，加工好
			// d c b a
			// 0 0 0 1
			int cur = 0;
			for (int i = 0; i < str.length(); i++) {
				cur ^= 1 << (str.charAt(i) - 'a');
			}
			// 一点点都不捣乱，cur，map有几个状态也是cur的字符串
			ans += status.getOrDefault(cur, 0);
			for (int i = 0; i < 26; i++) {
				// 每一位捣乱一下
				// a
				// b
				// c
				// z
				ans += status.getOrDefault(cur ^ (1 << i), 0);
			}
			status.put(cur, status.getOrDefault(cur, 0) + 1);
		}
		return ans;
	}

	// 为了验证
	public static String[] randomStringArray(int n, int m, int r) {
		String[] ans = new String[n];
		for (int i = 0; i < n; i++) {
			int len = (int) (Math.random() * m) + 1;
			char[] str = new char[len];
			for (int j = 0; j < len; j++) {
				str[j] = (char) ((int) (Math.random() * r) + 'a');
			}
			ans[i] = String.valueOf(str);
		}
		return ans;
	}

	public static void main(String[] args) {
		int N = 100;
		int M = 20;
		int R = 5;
		int testTime = 5000;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
			int n = (int) (Math.random() * N) + 1;
			String[] strs = randomStringArray(n, M, R);
			int ans1 = num1(strs);
			int ans2 = num2(strs);
			if (ans1 != ans2) {
				System.out.println("出错了!");
			}
		}
		System.out.println("测试结束");
	}

}