[ leetcode ] 859. Buddy Strings

두 string이 주어졌을 때, 서로 다른 두 위치의 값들을 한번만 바꿔 같은 string이 될 수 있으면 true를 return하고 그렇지 않으면 false를 return하는 문제입니다.

크게 두 가지 갈래로 나눌 수 있습니다. 두 string이 모두 같은 경우와 그렇지 않은 경우가 있습니다.

 

1. 두 string 같은 경우는 같은 문자가 포함되어 있지 않다면, 두 자리를 변경하면 같아질 수 없습니다.

    같은 문자가 포함된 경우를 판단하는 것은 set을 사용하여 기존 문자열과 길이가 달라지는 것으로 판단 가능합니다.

2. 다른 경우는 two point로 양쪽에서 index를 출발하여 같은 자리를 비교하며 같지 않은 index를 각각 저장해두고 그 두 자리를 변경했을 때 같지 않다면 같은 문자열을 만들 수 없다고 판단합니다.

 

#include <set>
#define swap(a,b,t)((t) = (a), (a) = (b), (b) = (t))

class Solution {
public:
    bool buddyStrings(string s, string goal) {
        if (s == goal) {	// 같은 문자열인 경우
            set<char> temp(s.begin(), s.end());
            return temp.size() < goal.size();  // 같은 문자 포함 시 길이가 줄어듦
        }

        int i = 0, j = goal.length() - 1, t;
        while (i < j && s[i] == goal[i]) i++;	// 서로 다른 인덱스 두가지를 찾아서 변경
        while (j >= 0 && s[j] == goal[j]) j--;

        swap(s[i], s[j], t);
        return s == goal;
    }
};