Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1061.html
1061. Lexicographically Smallest Equivalent String
Level
Medium
Description
Given strings A
and B
of the same length, we say A[i] and B[i] are equivalent characters. For example, if A = "abc"
and B = "cde"
, then we have 'a' == 'c'
, 'b' == 'd'
, 'c' == 'e'
.
Equivalent characters follow the usual rules of any equivalence relation:
- Reflexivity: ‘a’ == ‘a’
- Symmetry: ‘a’ == ‘b’ implies ‘b’ == ‘a’
- Transitivity: ‘a’ == ‘b’ and ‘b’ == ‘c’ implies ‘a’ == ‘c’
For example, given the equivalency information from A
and B
above, S = "eed"
, "acd"
, and "aab"
are equivalent strings, and "aab"
is the lexicographically smallest equivalent string of S
.
Return the lexicographically smallest equivalent string of S
by using the equivalency information from A
and B
.
Example 1:
Input: A = “parker”, B = “morris”, S = “parser”
Output: “makkek”
Explanation: Based on the equivalency information in A and B, we can group their characters as [m,p], [a,o], [k,r,s], [e,i]. The characters in each group are equivalent and sorted in lexicographical order. So the answer is “makkek”.
Example 2:
Input: A = “hello”, B = “world”, S = “hold”
Output: “hdld”
Explanation: Based on the equivalency information in A and B, we can group their characters as [h,w], [d,e,o], [l,r]. So only the second letter ‘o’ in S is changed to ‘d’, the answer is “hdld”.
Example 3:
*Input: A = “leetcode”, B = “programs”, S = “sourcecode”
Output: “aauaaaaada”
Explanation: We group the equivalent characters in A and B as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in S except ‘u’ and ‘d’ are transformed to ‘a’, the answer is “aauaaaaada”.
Note:
- String
A
,B
andS
consist of only lowercase English letters from'a'
-'z'
. - The lengths of string
A
,B
andS
are between1
and1000
. - String
A
andB
are of the same length.
Solution
Use two maps to store each letter with its group and each group with the letters in the group, respectively. Initially, all letters have different groups, and each group has only one letter, which is the letter itself.
Loop over A
and B
and merge each pair of letters into one group. When merging into one group, only remain the group that is lexicographically smallest. All the letters from both previous groups are mapped to the remaining group, and the remaining group is mapped to all the letters from both previous groups.
After the mappings are done, loop over S
and obtain the group for each letter and replace the letter in S
. Finally, return the new string.
-
class Solution { public String smallestEquivalentString(String A, String B, String S) { Map<Character, Character> letterGroupMap = new HashMap<Character, Character>(); Map<Character, Set<Character>> groupLettersMap = new HashMap<Character, Set<Character>>(); for (char c = 'a'; c <= 'z'; c++) { letterGroupMap.put(c, c); Set<Character> set = new HashSet<Character>(); set.add(c); groupLettersMap.put(c, set); } int length = A.length(); for (int i = 0; i < length; i++) { char c1 = A.charAt(i), c2 = B.charAt(i); char group1 = letterGroupMap.get(c1), group2 = letterGroupMap.get(c2); if (group1 != group2) { Set<Character> set1 = groupLettersMap.get(group1); Set<Character> set2 = groupLettersMap.get(group2); if (group1 < group2) { for (char c : set2) letterGroupMap.put(c, group1); set1.addAll(set2); groupLettersMap.put(group1, set1); groupLettersMap.remove(group2); } else { for (char c : set1) letterGroupMap.put(c, group2); set2.addAll(set1); groupLettersMap.put(group2, set2); groupLettersMap.remove(group1); } } } char[] array = S.toCharArray(); int strLength = array.length; for (int i = 0; i < strLength; i++) { char c = array[i]; char group = letterGroupMap.get(c); array[i] = group; } return new String(array); } }
-
class Solution: def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str: p = list(range(26)) def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] for i in range(len(s1)): a, b = ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a') pa, pb = find(a), find(b) if pa < pb: p[pb] = pa else: p[pa] = pb res = [] for a in baseStr: a = ord(a) - ord('a') res.append(chr(find(a) + ord('a'))) return ''.join(res)
-
class Solution { public: vector<int> p; string smallestEquivalentString(string s1, string s2, string baseStr) { p.resize(26); for (int i = 0; i < 26; ++i) p[i] = i; for (int i = 0; i < s1.size(); ++i) { int a = s1[i] - 'a', b = s2[i] - 'a'; int pa = find(a), pb = find(b); if (pa < pb) p[pb] = pa; else p[pa] = pb; } string res = ""; for (char a : baseStr) { char b = (char) (find(a - 'a') + 'a'); res += b; } return res; } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } };
-
var p []int func smallestEquivalentString(s1 string, s2 string, baseStr string) string { p = make([]int, 26) for i := 0; i < 26; i++ { p[i] = i } for i := 0; i < len(s1); i++ { a, b := int(s1[i]-'a'), int(s2[i]-'a') pa, pb := find(a), find(b) if pa < pb { p[pb] = pa } else { p[pa] = pb } } var res []byte for _, a := range baseStr { b := byte(find(int(a-'a'))) + 'a' res = append(res, b) } return string(res) } func find(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] }