[Java] LeetCode 1061. Lexicographically Smallest Equivalent String

[Java] LeetCode 1061. Lexicographically Smallest Equivalent String

 

문   제 : 

같은 길이의 문자열 s1, s2가 주어진다. 

s1[i] == s2[i] 조건이 성립한다. 

즉, 같은 인덱스의 문자들은 똑같다고 볼 수 있다.

이러한 방식으로 s1, s2에 속한 문자들을 그룹핑 해준다.

baseStr의 문자열을 업데이트 해준다.

※ 그 기준은

baseStr 문자열에서 한 문자씩 보며 그룹에 포함이 되어 있는 문자이면 해당 그룹에서 가장 사전순서상의 처음 오는 문자로 대치해준다.

 

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" and s2 = "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 )

Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"

Explanation: 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".

---

접   근 : 

Hash Set을 이용해 그룹핑해준다.

그룹핑한 Hash Set을 sort해서 baseStr을 업데이트 해준다.

 

---

해   결 : 

인덱스가 동일하거나, 같은 그룹에 이미 속해있는 문자들을 Hash Set을 이용해서 그룹핑해준다.
그룹핑 한 원소들을 ArrayList에 옮겨서 정렬해준다 - 사전순서(오름차순)
문자열 baseStr의 char[]형 배열인 charArray를 선언해준다.
baseStr의 문자들을 하나씩 검사하면서

Hash Set 그룹에 포함이 되어 있다면

sort한 ArrayList의 첫 번째 값으로 바꿔준다.

 

---

 

 

char를 원소로 갖는 Hash Set 을 선언한다.

HashSet<Character> set = new HashSet<Character>();

 

 

---

 

Hash Set에 s1, s2 문자열에서 같은 인덱스를 갖는 문자들을 먼저 그룹핑(add) 해준다.

set.add(s1.charAt(i));
set.add(s2.charAt(i));

 

---

 

반복문을 돌면서 s1, s2 문자열에서 추가로 그룹핑이 될 문자를 찾아서 그룹에 추가해준다.

※ 추가로 그룹이 될 문자의 기준 ※

    - 그룹에 속해 있는 문자와 연결된 또 다른 문자

 

Example)

a == b이고 set = [a, b] 인 상태에서

b == c 라는 사실을 알면 c 또한 그룹에 포함이 되는 것이다.

 

for(int j=0; j<s1.length(); j++){
    if(i != j && (set.contains(s1.charAt(j)) || set.contains(s2.charAt(j)))){
        set.add(s1.charAt(j));
        set.add(s2.charAt(j));
    }
}

 

---

 

그룹핑이 끝난 Hash Set을 ArrayList로 변환해 사전 순서대로(오름차) 정렬해준다.

// set sort
ArrayList<Character> sortSet = new ArrayList<>(set);
Collections.sort(sortSet);

 

---

 

baseStr 문자열을 char[] 형으로 저장할 변수를 선언해준다. (업데이트를 해주기 위함)

 

baseStr을 돌면서 Hash Set에 포함이 되어 있는 문자가 있으면,

해당 그룹의 사전 순서의 제일 첫 번째로 오는 문자로 바꿔준다.

 

바꿔주는 반복문이 끝나면 baseStr 문자열을 업데이트 해준다.

// baseStr update
char[] charArray = baseStr.toCharArray();
for(int j=0; j<baseStr.length(); j++){
    if(set.contains(baseStr.charAt(j))){
        charArray[j] = sortSet.get(0);
    }
}
baseStr = String.valueOf(charArray);

 

---

결   과  :

class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        

        for(int i=0; i<s1.length(); i++){

            HashSet<Character> set = new HashSet<Character>();
            set.add(s1.charAt(i));
            set.add(s2.charAt(i));

            for(int j=0; j<s1.length(); j++){
                if(i != j && (set.contains(s1.charAt(j)) || set.contains(s2.charAt(j)))){
                    set.add(s1.charAt(j));
                    set.add(s2.charAt(j));
                }
            }
            
            // set sort
            ArrayList<Character> sortSet = new ArrayList<>(set);
            Collections.sort(sortSet);

            // baseStr update
            char[] charArray = baseStr.toCharArray();
            for(int j=0; j<baseStr.length(); j++){
                if(set.contains(baseStr.charAt(j))){
                    charArray[j] = sortSet.get(0);
                }
            }
            baseStr = String.valueOf(charArray);
            
        }

        return baseStr;
    }
}