[LeetCode] 1657. Determine if Two Strings Are Close

🔈 문제

Two strings are considered close if you can attain one from the other using the following operations:

Operation 1: Swap any two existing characters.For example, abcde -> aecdb
Operation 2: Transform every occurrence of one existing character into another existing character, and do the same
with the other character. For example, aacabb -> bbcbaa (all a's turn into b's, and all b's turn into a's)
You can use the operations on either string as many times as necessary.
Given two strings, word1 and word2, return true if word1 and word2 are close, and false otherwise.

 

💫 예시

Input: word1 = "abc", word2 = "bca"
Output: true
Explanation: You can attain word2 from word1 in 2 operations. Apply Operation 1: "abc" -> "acb" Apply Operation 1: "acb" -> "bca"

 

 

📚 문제 풀이

이 문제에서 우리가 할 수 있는 옵션은 주어진 문자열 중 두 개의 위치를 스왑하는 것과 주어진 문자열 중 두 종류의 문자를 골라 그 종류 전체를 스왑하는 것이다. 

 

정리해보자면 주어진 문자열에서 완전히 새로운 알파벳을 추가할 수는 없고, 알파벳이 등장하는 수들의 값들은 변하지 않는다.

 

aabbb에서 오퍼레이션 2를 적용하면 bbaaa가 된다. 

작업을 하기 전에는 a가 2개, b가 3개 있었고, 작업 적용 후에는 a가 3개, b가 2개가 되었다. 2와 3의 값은 변하지 않았고, 문자열에 포함되어 있는 알파벳 a와b도 여전히 존재하고 있다.

 

이 문제를 해결하기 위해서는 word1과 word2에 존재하는 알파벳이 같은지, 그리고 등장하는 알파벳 갯수가 서로 동일한지를 파악하면 된다.

 

파이썬에서는 Counter를 사용하면 바로 문자열에서 문자가 몇 번 등장하였는지 세준다. (dict 형)

 

코드포스에서 볼법한 문제였다.

 

💻 코드

python

 

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        cnt1 = Counter(word1)
        cnt2 = Counter(word2)
        return cnt1.keys() == cnt2.keys() and sorted(cnt1.values()) == sorted(cnt2.values())

 

 

java

 

class Solution {
    public boolean closeStrings(String word1, String word2) {
        Map<Character, Integer> cnt1 = generateCnt(word1);
        Map<Character, Integer> cnt2 = generateCnt(word2);
        List<Integer> val1 = new ArrayList<>(cnt1.values());
        List<Integer> val2 = new ArrayList<>(cnt2.values());
        Collections.sort(val1);
        Collections.sort(val2);
        return Objects.equals(cnt1.keySet(), cnt2.keySet()) && Objects.equals(val1, val2);
    }
    
    public Map<Character, Integer> generateCnt(String word) {
        Map<Character, Integer> res = new HashMap<>();
        for (int i = 0; i < word.length(); i++) {
            int val = res.getOrDefault(word.charAt(i), 0);
            res.put(word.charAt(i), val + 1);
        }
        return res;
    }
}

 

 

🔗 문제링크 

Determine if Two Strings Are Close - LeetCode