aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--lexicographically_small_string.c44
-rw-r--r--lexicographically_smallest_equivalent_str.c46
-rw-r--r--lexicographically_smallest_equivalent_str.py49
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")
+ )