[leetcode] 1657. Determine if Two Strings Are Close

문제

 

1. 문제 해석

두 string이 close한지 판단하는 문제

 

close 한 기준은 두 개의 operation을 시도했을 때 부합했을 경우이다.

• Operation 1: 두 개의 요소의 위치를 바꾸었을 때
  • For example, abcde -> aecdb

• Operation 2: Operation1을 기반으로 한 글자의 위치에 다른 글자로 모두 대체하고 반대로도 시행했을 경우
  • For example, aacabb -> bbcbaa (all a's turn into b's, and all b's turn into a's)

부합할 경우 true, 아닐 경우 false

 

2. 문제 풀이 방향

1. 주어진 두 개의 string의 character와 character's occurence를 조사한다. 
2. 조사한 두 string의 character 가 다를 경우 false를 반환한다. (Operation 1 불가)
3. 2번이 true일 경우 character's occurence를 정렬해서 다른 값이 확인될 경우 false를 반환한다. (Operation 2 불가)
4. Operation 1 & Operation 2 를 모두 통과했음으로 true를 반환한다.

 

Java, Kotlin 코드

import java.util.*;

class Solution {
    public boolean closeStrings(String word1, String word2) {
        Map<Character, Integer> map1 = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();

        for(int i = 0; i < word1.length(); i++) {
            char a = word1.charAt(i);

            map1.put(a, map1.getOrDefault(a, 0) + 1);
        }

        for(int i = 0; i < word2.length(); i++) {
            char a = word2.charAt(i);

            map2.put(a, map2.getOrDefault(a, 0) + 1);
        }

        List<Character> keys1 = new ArrayList<>(map1.keySet());
        List<Character> keys2 = new ArrayList<>(map2.keySet());

        List<Integer> values1 = new ArrayList<>(map1.values()); 
        List<Integer> values2 = new ArrayList<>(map2.values()); 

        Collections.sort(keys1);
        Collections.sort(keys2);

        if (keys1.size() != keys2.size()) {
            return false;
        }

        for(int i = 0; i < keys1.size(); i++) {
            if (keys1.get(i) != keys2.get(i)) {
                return false;
            }
        }

        Collections.sort(values1);
        Collections.sort(values2);

        if (values1.size() != values2.size()) {
            return false;
        }

        for(int i = 0; i < values1.size(); i++) {
            if ((int)values1.get(i) != (int)values2.get(i)) {
                return false;
            }
        }

        return true;
    }
}

class Solution {
    fun closeStrings(word1: String, word2: String): Boolean {
        val arr1 = IntArray(26)
        val arr2 = IntArray(26)

        for(index in word1.indices) {
            arr1[word1[index] - 'a']++
        }

        for(index in word2.indices) {
            arr2[word2[index] - 'a']++
        }

        for(index in arr1.indices) {
            if((arr1[index] == 0 && arr2[index] != 0) || (arr1[index] != 0 && arr2[index] == 0)) {
                return false
            }
        }

        arr1.sort()
        arr2.sort()

        return arr1 contentEquals arr2
    }
}