diff options
Diffstat (limited to 'lexicographically_small_string.c')
-rw-r--r-- | lexicographically_small_string.c | 44 |
1 files changed, 0 insertions, 44 deletions
diff --git a/lexicographically_small_string.c b/lexicographically_small_string.c deleted file mode 100644 index e635184..0000000 --- a/lexicographically_small_string.c +++ /dev/null @@ -1,44 +0,0 @@ -#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 -} |