https://leetcode.com/problems/lexicographically-smallest-equivalent-string/description/
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.
- For example, if
s1 = "abc"ands2 = "cde", then we have'a' == 'c','b' == 'd', and'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 s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr. Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.
Example 1:
|
1 2 3 4 5 |
<strong>Input:</strong> s1 = "parker", s2 = "morris", baseStr = "parser" <strong>Output:</strong> "makkek" <strong>Explanation:</strong> Based on the equivalency information in s1 and s2, 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". |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
class Solution { public String smallestEquivalentString(String s1, String s2, String baseStr) { //parent array int[] parent = new int[26]; //populate the parent array //initially assign parent of an element to itself for(int i=0;i<parent.length;i++){ parent[i] = i; } char[] s1Arr = s1.toCharArray(); char[] s2Arr = s2.toCharArray(); //process strings s1 and s2 for(int i=0;i<s1Arr.length;i++){ //get integer val: a-> 0, b-> 1 ... int a = s1Arr[i]-'a'; int b = s2Arr[i]-'a'; //union union(parent, a, b); } char[] baseStrArr = baseStr.toCharArray(); StringBuilder sb = new StringBuilder(); for(int i=0;i<baseStrArr.length;i++){ int a = baseStrArr[i]-'a'; int p = find(parent, a); sb.append((char)(p+'a')); } return sb.toString(); } private void union(int[] parent, int a, int b){ //get parent of a int parentA = find(parent, a); //get parent of b int parentB = find(parent, b); //which ever is smaller make it the parent of the other if(parentA < parentB){ parent[parentB] = parentA; } else { parent[parentA] = parentB; } } private int find(int[] parent, int a){ while(parent[a]!=a){ a = parent[a]; } return a; } } |