aboutsummaryrefslogtreecommitdiff
path: root/lexicographically_small_string.c
blob: e635184b4bf7e494271f8f120e1f0cb2a6f61eb9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int unionFind(int *u, int val) {
  if (u[val] == val)
    return val;
  return unionFind(u, u[val]);
}

bool unionSet(int *u, int a, int b) {
  int findA = unionFind(u, a), findB = unionFind(u, b);
  if (findA == findB)
    return false;
  if (findA < findB)
    u[findB] = u[findA];
  else
    u[findA] = u[findB];
  return true;
}

char *smallestEquivalentString(char *s1, char *s2, char *baseStr) {
  int *table = malloc(26 * sizeof(int));
  for (int i = 0; i < 26; i++)
    table[i] = i;
  for (int i = 0; i < strlen(s1); i++)
    unionSet(table, s1[i] - 'a', s2[i] - 'a');
  int ansLen = strlen(baseStr);
  char *ans = malloc((ansLen + 1) * sizeof(int));
  ans[ansLen] = '\0';
  for (int i = 0; i < ansLen; i++)
    ans[i] = unionFind(table, baseStr[i] - 'a') + 'a';
  return ans;
}

int main() {
  printf("%s\n", smallestEquivalentString("parker", "morris",
                                          "parser")); // expect: makkek
  printf("%s\n",
         smallestEquivalentString("hello", "world", "hold")); // expect: hdld
  printf("%s\n", smallestEquivalentString("leetcode", "programs",
                                          "sourcecode")); // expect: aauaaaaada
}