[leetcode][1657] Determine if Two Strings Are Close

문제 : leetcode.com/problems/determine-if-two-strings-are-close/

---

1. 문자열에서 어떤 두 문자의 위치를 바꾼다. ex) abcde -> aecdb (b, e 교환)

2. 문자열에 존재하는 두 문자들을 모두 바꾼다. ex) aacabb -> bbcbaa (a, b 교환)

 

word1 문자열에 위 두 연산을 해서 word2 문자열을 만들 수 있는지 구하라.

---

word1 문자열을 앞에서부터 탐색하면서 두 연산을 실행시켜가면서 word2 문자열을 구해봐야하나 싶지만 더 간단한 방법이 있다.

1번 연산은 문자열의 문자 위치는 변경가능하므로 위치는 무의미하다는 것을 의미한다.

즉, word1, word2의 문자들의 개수(a의 개수, b의 개수 ... )만 맞출 수 있다면 word1에서 word2 문자열을 만들 수 있다.

2번 연산은 각 문자의 등장횟수를 교환할 수 있다. aaabb 문자열에서 a, b문자들을 바꾸면 bbaaa가 되고 a문자, b문자의 등장횟수가 3,2에서 2,3으로 변경됨을 확인할 수 있다.

 

따라서 word1 문자열을 word2 문자열로 만들 수 있는 경우는 아래와 같은 조건들을 만족해야한다.

1. word1, word2 문자열들에 등장하는 문자들의 종류가 동일해야 한다.

2. word1, word2 문자열에서 모든 소문자들의 등장횟수를 저장한 배열을 정렬했을 때, 두 배열은 동일해야 한다.

 

N = |word1|, M = |word2|. 시간복잡도는 O(N + M).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/1657.%20Determine%20if%20Two%20Strings%20Are%20Close.cpp