Here is the post.
I spent 30 minutes in weekly contest 155 on the algorithm first, and I continued to spend over an hour to complete the code on Sept. 23, 2019. I made a lot of errors, but I like the experience to solve the problem using union find algorithm. My plan is to be able to solve it in less than 30 minutes in total in short future.
Here are highlights.
- Understand union find algorithm, disjoint set, write findParent, union two APIs;
- Do not mix parent[i] with findParent(int[] parent, int node), the latter one has path compression functionality. Do not call parent[i] directly, call findParent;
- SortedSet is not applied, since same char can have multiple occurrences in one disjoint set;
- Each disjoint set should be sorted first as a char array, and then push to Queue;
- I ran into stack overflow bug, so I modified union function, replace parent[i] with findParent(int[] parent, int node);
- Design variable disjointSets using Dictionary<int, List>; SortedSet is not working for duplicated chars in string test case, for example: "abcmdem", m has two occurrences.
- Design sortedStrings using Dictionary<int, Queue>; Queue is chosen since it is easy to iterate for each disjiont set.
The following code passes online judge, but I may have to review the code to simplify the code.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace unionFind
{
class Program
{
static void Main(string[] args)
{
RunTestcase1();
//RunTestcase2();
}
public static void RunTestcase1()
{
var pairs = new List<IList<int>>();
pairs.Add((new int[]{0, 3}).ToList());
pairs.Add((new int[]{1, 2}).ToList());
var result = SmallestStringWithSwaps("dcab", pairs);
Debug.Assert(result.CompareTo("bacd") == 0);
}
public static void RunTestcase2()
{
var pairs = new List<IList<int>>();
pairs.Add((new int[] { 0, 3 }).ToList());
pairs.Add((new int[] { 1, 2 }).ToList());
pairs.Add((new int[] { 0, 2 }).ToList());
var result = SmallestStringWithSwaps("dcab", pairs);
Debug.Assert(result.CompareTo("abcd") == 0);
}
/// <summary>
/// Leetcode 1202 - small string
/// </summary>
/// <param name="s"></param>
/// <param name="pairs"></param>
/// <returns></returns>
public static string SmallestStringWithSwaps(string s, IList<IList<int>> pairs)
{
var length = s.Length;
var parent = new int[length];
for (int i = 0; i < length; i++)
{
parent[i] = i;
}
foreach (var pair in pairs)
{
var first = pair[0];
var second = pair[1];
if (findParent(parent, first) != findParent(parent, second))
{
// union two set;
union(parent, parent[first], parent[second]);
}
}
// allow duplicate char in string
var disjointSets = new Dictionary<int, List<char>>();
for (int i = 0; i < length; i++)
{
var key = findParent(parent, i);
if (!disjointSets.ContainsKey(key))
{
disjointSets.Add(key, new List<char>());
}
disjointSets[key].Add(s[i]);
}
// sorting
var sortedStrings = new Dictionary<int, Queue<char>>();
foreach (var pair in disjointSets)
{
var list = pair.Value;
var array = list.ToArray();
Array.Sort(array);
var queue = new Queue<char>();
foreach(var item in array)
queue.Enqueue(item);
sortedStrings.Add(pair.Key, queue);
}
var sb = new StringBuilder();
for (int i = 0; i < length; i++)
{
var key = findParent(parent, i);
var value = sortedStrings[key].Dequeue();
sb.Append(value);
}
return sb.ToString();
}
/// <summary>
/// path compression
/// </summary>
/// <param name="parent"></param>
/// <param name="node"></param>
/// <returns></returns>
private static int findParent(int[] parent, int node)
{
return node == parent[node] ? node : parent[node] = findParent(parent, parent[node]);
}
/// <summary>
/// Simplify API
/// </summary>
/// <param name="parent"></param>
/// <param name="first"></param>
/// <param name="second"></param>
private static void union(int[] parent, int first, int second)
{
var firstParent = findParent(parent, first);
var secondParent = findParent(parent, second);
if(firstParent == secondParent)
return;
parent[firstParent] = secondParent;
}
}
}
