前言
一题多解，打开格局与视野，Pre-Graph + component-DFS类型，也可使用并查集将两个有相似节点的树进行合并，合并一次，连通分量少一个。
一、案例
二、题解
1）Pre-Graph + component-循环DFS|BFS（朴素处理法，虚节点处理法。）
2）并查集，将两个有相同节点的树合并在一起。
package com.xhu.offer.offerII;
import java.util.*;
//想似的字符串
public class NumSimilarGroups {
//Pre-Graph + 求有多少连通分量
//Pre-Graph:1-朴素做法：生成邻接矩阵，字符串为节点，两两比较，看是否有两个位置不同，且这两个位置刚好相反，如果是表示两字符串相连，否则不相连。
// 2-虚节点：产生strs中每个字符串各种顺序交换行成虚节点，采用邻接表作为改图的物理结构。
//求有多少连通分量：以每个节点为始进行DFS，该节点访问过就continue，否则count++，那么count就为改图的连通分量。
public int numSimilarGroups(String[] strs) {
Set<String> ori = new HashSet<>();
for (String str : strs) ori.add(str);//生成的虚拟节点必须是原字符串数组中的。
//Pre-Graph
for (String str : strs) {
if (nodeNum == strs.length) break;
addEdge(str, ori);
}
//循环DFS求连通分量个数
int count = 0;
int[] visited = new int[nodeNum];
for (String str : strs) {
if (visited[nodes.get(str)] != 1) {
count++;
dfs(str, visited);
}
}
return count;
}
/**
* 对与起点节点能相连的节点进行标记
*
* @param str 起点节点
* @param visited
*/
private void dfs(String str, int[] visited) {
//开始进行DFS
int id = nodes.get(str);
visited[nodes.get(str)] = 1;//表示已经访问过。
Set<Integer> original = edges.get(id);
for (Integer other : original) {
if (visited[other] == 0) dfs(reflect.get(other), visited);
}
}
/**
* 构建虚节点之间的边。
*
* @param str
*/
private void addEdge(String str, Set<String> ori) {
addNode(str);
//生成虚节点，并与str节点进行连接
List<String> virtualNodes = produceVirtualNodes(str, ori);
//添加虚节点，并添加原节点与虚节点的相连边
int idx1 = nodes.get(str);
for (String virtualNode : virtualNodes) {
addNode(virtualNode);
int idx2 = nodes.get(virtualNode);
//无向图，相互连接
edges.get(idx1).add(idx2);
edges.get(idx2).add(idx1);
}
}
/**
* 生成虚拟节点集合
*
* @param str 根据str来生成符合条件的虚拟节点
* @param ori 生成的虚拟节点在ori中才满足条件。
* @return
*/
private List<String> produceVirtualNodes(String str, Set<String> ori) {
int len = str.length();
char[] chs = str.toCharArray();
List<String> nodes = new ArrayList<>();
for (int i = 0; i < len - 1; i++) {
char beginCh = chs[i];
for (int j = i + 1; j < len; j++) {
char endCh = chs[j];
chs[i] = endCh;
chs[j] = beginCh;
String s = String.valueOf(chs);
if (ori.contains(s)) nodes.add(s);
//还原字符数组
chs[i] = beginCh;
chs[j] = endCh;
}
}
return nodes;
}
/**
* 添加节点，并进行hash映射，生成邻接数组。
*
* @param str
*/
private void addNode(String str) {
if (!nodes.containsKey(str)) {
nodes.put(str, nodeNum++);
edges.add(new HashSet<>());
reflect.add(str);
}
}
Map<String, Integer> nodes = new HashMap<>();//把字符串当作一个节点，并编号为邻接数组做准备。
List<Set<Integer>> edges = new ArrayList<>();//通过编号构建邻接矩阵。
int nodeNum;//记录节点数并为邻接数组做准备。
List<String> reflect = new ArrayList<>();//数组hash，根据编号得到str
}
class NumSimilarGroups2 {
//Pre-Graph + 求有多少连通分量
//Pre-Graph:1-朴素做法：两两比较，看是否有两个位置不同，如果是表示两字符串相连，否则不相连。
// 2-虚节点：产生strs中每个字符串各种顺序交换行成虚节点。这里题目做了限制，这种做法就适得其反。
//求有多少连通分量：以每个节点为始进行DFS，该节点访问过就continue，否则count++，那么count就为改图的连通分量。
public int numSimilarGroups(String[] strs) {
Set<String> ori = new HashSet<>();
for (String str : strs) ori.add(str);//生成的虚拟节点必须是原字符串数组中的。
//Pre-Graph
for (String str : strs) {
addEdge(str, ori);
}
//循环DFS求连通分量个数
int count = 0;
for (String str : strs) {
if (ori.contains(str)) {
count++;
dfs(str, ori);
}
}
return count;
}
/**
* 对与起点节点能相连的节点进行标记，标记的方式为直接删除。
*
* @param str 起点节点
*/
private void dfs(String str, Set<String> ori) {
//开始进行DFS
ori.remove(str);//表示已经访问过。
Set<String> original = graph.get(str);
for (String s : original) {
if (ori.contains(s)) dfs(s, ori);
}
}
/**
* 将相似单词连接上
*
* @param str
*/
private void addEdge(String str, Set<String> ori) {
addNode(str);
Set<String> edge1 = graph.get(str);
for (String node : ori) {
if (similar(str, node)) {
addNode(node);
edge1.add(node);
graph.get(node).add(str);
}
}
}
/**
* 判断两个字符串是否相似；
* 这里以朴素化的方式来做，因为虚节点方式大可不必，原因在于题目做了限制，限制strs中所有单词都为字母异位词。
*
* @param str
* @param node
* @return
*/
private boolean similar(String str, String node) {
int cnt = 0, len = str.length();
for (int i = 0; i < len; i++) {
if (str.charAt(i) != node.charAt(i)) cnt++;
if (cnt > 2) return false;
}
return cnt == 2;
}
/**
* 添加节点，并进行hash映射，生成邻接数组。
*
* @param str
*/
private void addNode(String str) {
if (!graph.containsKey(str)) graph.put(str, new HashSet<>());
}
Map<String, Set<String>> graph = new HashMap<>();//图的物理结构
}
class NumSimilarGroups3 {
//并查集
public int numSimilarGroups(String[] strs) {
int n = strs.length;
int[] father = new int[n];
for (int i = 0; i < n; i++) father[i] = i;
int count = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (similar(strs[i], strs[j]) && union(father, i, j)) {
count--;
}
}
}
return count;
}
/**
* 合并子树
*
* @param father
* @param i
* @param j
* @return
*/
private boolean union(int[] father, int i, int j) {
//寻找该子树的根节点
int root1 = findFather(father, i);
int root2 = findFather(father, j);
//合并两子树
if (root1 != root2) {
father[root1] = root2;
return true;
}
return false;
}
/**
* 找根节点（易理解版，构成一颗有深度的树，即有多次分支。）
*
* @param father
* @param idx
* @return
*/
private int findFather(int[] father, int idx) {
if (idx == father[idx]) return father[idx];
int root = findFather(father, father[idx]);
return root;
}
/**
* 每次查找时就顺便改变树结构，可简化代码
*
* @param father
* @param idx
* @return
*/
private int findFather2(int[] father, int idx) {
if (idx != father[idx])
father[idx] = findFather2(father, father[idx]);
return father[idx];
}
/**
* 相似度判断
*
* @param s
* @param another
* @return
*/
private boolean similar(String s, String another) {
int cnt = 0;
int len = s.length();
for (int i = 0; i < len; i++) {
if (s.charAt(i) != another.charAt(i)) ++cnt;
if (cnt > 2) return false;
}
return 1 != cnt;
}
}
总结
1）深入理解并查集的思想，做到其它问题与并查集的转换。
2）一题多解，打开格局与视野。
参考文献
[1] LeetCode 想似的字符串