diff options
-rw-r--r-- | lexicographically_small_string.c | 44 | ||||
-rw-r--r-- | lexicographically_smallest_equivalent_str.c | 46 | ||||
-rw-r--r-- | lexicographically_smallest_equivalent_str.py | 49 |
3 files changed, 95 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 -} diff --git a/lexicographically_smallest_equivalent_str.c b/lexicographically_smallest_equivalent_str.c new file mode 100644 index 0000000..f1b4939 --- /dev/null +++ b/lexicographically_smallest_equivalent_str.c @@ -0,0 +1,46 @@ +// 1061. Lexicographically Smallest Equivalent String +#include "leetcode.h" + +/* + * you are given two strings of the same length 's1' and 's2' and a string + * 'baseStr'. we say 's1[i]' and 's2[i]' are equivalent characters. equivalent + * characters follow the usual rules of any equivalence relation: reflexivity, + * symmetry, and transitivity. return the lexicographically smallest equivalent + * string of 'baseStr' by using the equivalency information from 's1' and 's2'. + */ + +char *smallestEquivalentString(char *s1, char *s2, char *baseStr) { + char *ans = baseStr, table[26], to_rep, rep_with; + for (int i = 0; i < 26; i++) + table[i] = i + 'a'; + while (*s1) { + if (table[*s2 - 'a'] < table[*s1 - 'a']) { + to_rep = table[*s1 - 'a']; + rep_with = table[*s2 - 'a']; + for (int i = 0; i < 26; i++) + if (table[i] == to_rep) + table[i] = rep_with; + } else if (table[*s1 - 'a'] < table[*s2 - 'a']) { + to_rep = table[*s2 - 'a']; + rep_with = table[*s1 - 'a']; + for (int i = 0; i < 26; i++) + if (table[i] == to_rep) + table[i] = rep_with; + } + s1++, s2++; + } + while (*baseStr) { + *baseStr = table[*baseStr - 'a']; + baseStr++; + } + return ans; +} + +int main() { + char *s11 = "parker", *s21 = "morris", *b1 = "parser"; + char *s12 = "hello", *s22 = "world", *b2 = "hold"; + char *s13 = "leetcode", *s23 = "programs", *b3 = "sourcecode"; + printf("%s\n", smallestEquivalentString(s11, s21, b1)); // expect: makkek + printf("%s\n", smallestEquivalentString(s12, s22, b2)); // expect: hdld + printf("%s\n", smallestEquivalentString(s13, s23, b3)); // expect: aauaaaaada +} diff --git a/lexicographically_smallest_equivalent_str.py b/lexicographically_smallest_equivalent_str.py new file mode 100644 index 0000000..534d844 --- /dev/null +++ b/lexicographically_smallest_equivalent_str.py @@ -0,0 +1,49 @@ +# 1061. Lexicographically Smallest Equivalent String + +""" +you are given two strings of the same length 's1' and 's2' and a string +'baseStr'. we say 's1[i]' and 's2[i]' are equivalent characters. equivalent +characters follow the usual rules of any equivalence relation: reflexivity, +symmetry, and transitivity. return the lexicographically smallest equivalent +string of 'baseStr' by using the equivalency information from 's1' and 's2'. +""" + + +class Solution(object): + def smallestEquivalentString(self, s1, s2, baseStr): + """ + :type s1: str + :type s2: str + :type baseStr: str + :rtype: str + """ + uf = {} + + def find(x): + uf.setdefault(x, x) + if x != uf[x]: + uf[x] = find(uf[x]) + return uf[x] + + def union(x, y): + rx, ry = find(x), find(y) + if rx > ry: + uf[rx] = ry + else: + uf[ry] = rx + + for i in range(len(s1)): + union(s1[i], s2[i]) + ans = [] + for i in baseStr: + ans.append(find(i)) + return "".join(ans) + + +if __name__ == "__main__": + obj = Solution() + print(obj.smallestEquivalentString(s1="parker", s2="morris", baseStr="parser")) + print(obj.smallestEquivalentString(s1="hello", s2="world", baseStr="hold")) + print( + obj.smallestEquivalentString(s1="leetcode", s2="programs", baseStr="sourcecode") + ) |