广度搜索+哈希表+状态转换

 

贴代码：

 

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;

class Solution {
	Map<Integer, Integer> map = new HashMap<>();
	HashSet<Integer> set = new HashSet<>();

	public int[] groupStrings(String[] words) {
		int n = words.length;

		// 转换
		for (int i = 0; i < n; i++) {
			String s = words[i];
			int mark = 0;
			for (int j = 0, len = s.length(); j < len; j++) {
				int v = s.charAt(j) - 'a';
				mark += (1 << v);
			}
			Integer v = map.get(mark);
			if (v == null) {
				map.put(mark, 1);
			} else {
				map.put(mark, v + 1);
			}
		}

		// bfs;
		int max = 0;
		int total = 0;

		for (Entry<Integer, Integer> entry : map.entrySet()) {
			int u = entry.getKey();

			if (set.contains(u)) {
				continue;
			}
			total++;
			// 0 变 1
			// 1 变 0
			// 替换. count0,count1,
			int num = bfs(u);
			if (num > max) {
				max = num;
			}
		}
		return new int[] { total, max };
	}

	public int bfs(int root) {
		int cnt = map.get(root);
		Queue<Integer> queue = new LinkedList<>();
		queue.add(root);
		set.add(root);

		while (!queue.isEmpty()) {
			int u = queue.poll();

			// add;
			for (int i = 0; i < 26; i++) {
				if ((u & (1 << i)) == 0) {
					int v = u + (1 << i);

					Integer num = map.get(v);

					if (num == null) {
						continue;
					}

					if (set.contains(v)) {
						continue;
					}

					queue.add(v);
					set.add(v);
					cnt += num;
				}
			}
			// delete;
			for (int i = 0; i < 26; i++) {
				if ((u & (1 << i)) > 0) {
					int v = u - (1 << i);

					Integer num = map.get(v);
					if (num == null) {
						continue;

					}

					if (set.contains(v)) {
						continue;
					}

					queue.add(v);
					set.add(v);
					cnt += num;

				}
			}
			// transfer;
			for (int i = 0; i < 26; i++) {
				if ((u & (1 << i)) > 0) {
					for (int j = 0; j < 26; j++) {
						if( (u & (1<<j)) == 0){
							int v = u - (1<<i) + (1<<j);
							
							Integer num = map.get(v);
							if(num == null){
								continue;
							}
							
							if( set.contains(v)){
								continue;
							}
							
							queue.add(v);
							set.add(v);
							cnt += num;
						}
					}
				}
			}
		}

		return cnt;
	}

}