LeetCode (C/C++, Java) 2337. Move Pieces to Obtain a String

https://leetcode.com/problems/move-pieces-to-obtain-a-string/description/

 

---

풀이

문제에서 L은 왼쪽으로만, R은 오른쪽으로만 움직일 수 있다.

또한 해당 알파벳의 순서는 변할 수 없다. LRL로 입력된 문자열이라면 이 순서가 RLL, LLR등으로 바뀔 수 없다.

 

따라서 앞에서부터 차례로 순회하며 현재 만난 알파벳의 종류가 같은지 확인하며 탐색한다.

또한 target의 L 위치는 항상 start보다 왼쪽에 있어야 하고, R의 위치는 오른쪽에 있어야 한다.

---

C/C++ 코드

class Solution {
public:
    bool canChange(string start, string target) {
        int sIdx = 0, tIdx = 0;
        
        while (tIdx < target.size() || sIdx < start.size()) {
            while (tIdx < target.size() && target[tIdx] == '_') tIdx++;
            while (sIdx < start.size() && start[sIdx] == '_') sIdx++;

            if (target[tIdx] != start[sIdx]) return false;
            
            if (target[tIdx] == 'L' && sIdx < tIdx) return false;
            if (target[tIdx] == 'R' && tIdx < sIdx) return false;
            
            sIdx++;
            tIdx++;
        }

        return true;
    }
};

 

Java 코드

class Solution {
    public boolean canChange(String start, String target) {
        int size = start.length();

        for (int i = 0, j = 0; i < size || j < size; i++, j++) {
            while (i < size && start.charAt(i) == '_') i++;
            while (j < size && target.charAt(j) == '_') j++;

            if (i == size || j == size)
                return i == j;

            if (start.charAt(i) != target.charAt(j)) return false;
            if (start.charAt(i) == 'L' && i < j) return false;
            if (start.charAt(i) == 'R' && j < i) return false;
        }
        return true;
    }
}