839. Similar String Groups
Approach
DFS to find connected components; two strings are similar if they are equal or differ in exactly 2 positions.
Key Techniques
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.
// Approach: DFS to find connected components; two strings are similar if they are equal or differ in exactly 2 positions.
// Time: O(n² · m) Space: O(n)
public class Solution
{
public int NumSimilarGroups(string[] strs)
{
int groups = 0, n = strs.Length;
int[] vis = new int[n];
for (int i = 0; i < n; i++)
{
if (vis[i] == 1)
continue;
groups++;
DFS(i, strs, vis);
}
return groups;
}
private void DFS(int i, string[] strs, int[] vis)
{
vis[i] = 1;
for (int j = 0; j < strs.Length; j++)
{
if (vis[j] == 1)
continue;
if (IsSimiliar(strs[i], strs[j]))
DFS(j, strs, vis);
}
}
bool IsSimiliar(string a, string b)
{
int cnt = 0;
for (int i = 0; i < a.Length; i++)
{
if (a[i] != b[i])
cnt++;
}
return cnt == 2 || cnt == 0;
}
}