aboutsummaryrefslogtreecommitdiff
path: root/lexicographically_smallest_equivalent_str.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-06-04 18:29:40 -0600
committerJack Sangdahl <[email protected]>2025-06-04 18:29:40 -0600
commita05784326180667fd695dd35d97dce314ab0a31c (patch)
treea9f0c59d9d7078ab5f44dfb333e9807930ff771c /lexicographically_smallest_equivalent_str.c
parentbc5339f3d4c2251937712cbe65bed32f2e0ab5b6 (diff)
downloadleetcode-a05784326180667fd695dd35d97dce314ab0a31c.tar.gz
leetcode-a05784326180667fd695dd35d97dce314ab0a31c.zip
1061. lexicographically smallest equivalent string
Diffstat (limited to 'lexicographically_smallest_equivalent_str.c')
-rw-r--r--lexicographically_smallest_equivalent_str.c46
1 files changed, 46 insertions, 0 deletions
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
+}