[LeetCode] 2337. Move Pieces to Obtain a String

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

leetcode - Move Pieces to Obtain a String

문제 유형: 투 포인터, 문자열 처리, 그리디

문제 난이도: Medium

 

문제

You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where:

• The characters 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right.
• The character '_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces.

Return true if it is possible to obtain the string target by moving the pieces of the string start any number of times. Otherwise, return false.

 

풀이

_는 중요하지 않다. 중요한 것은 start와 target의 L, R들의 순서, 그리고 상대적 위치차이 뿐이다.

두 문자열의 start의 길이까지만 신경쓰면 된다. 

두 문자열 start와 target을 순차적으로 읽을 것이다.

start[i], target[j]가 '_'인 동안은 쭉 통과한다.

그러고, start[i]와 target[j]가 다르다면, false를 반환한다. 순서가 다르기 때문이다.

start[i]가 'L'이고, i < j라면, false를 반환한다. i에서 j로 밀어야 하는데, L은 오른쪽으로 밀 수 없기 때문이다.

start[i]가 'R'이고, i > j라면, false를 반환한다. i에서 j로 밀어야 하는데, R은 왼쪽으로 밀 수 없기 때문이다.

 

코드

C++

class Solution {
public:
    bool canChange(string start, string target) {
        int n = start.size();

        for(int i = 0, j = 0; i < n || j < n; ++i, ++j) {
            while(i < n && start[i] == '_') ++i;
            while(j < n && target[j] == '_') ++j;

            char ch = start[i];
            if(ch != target[j]) return false;
            if(ch == 'L' && i < j) return false;
            if(ch == 'R' && i > j) return false;
        }

        return true;
    }
};