2337. Move Pieces to Obtain a String

難度: Medium

類型: Two Pointers, String

C程式下載: 2337.c

前情題要:

一個給定的 String, 一個 target String, 每個 String 都由 "R", "L" 與 "_" 構成。

"R" 可以向右移動如果右邊是 blank "_"。

"L" 可以向左移動如果左邊是 blank "_"。

如果給定的 String 可以透過 "L", "R" 的移動可以組成 target String, 則回傳 true。若是不行則回傳false。

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.

 

Example 1:

Input: start = "_L__R__R_", target = "L______RR"
Output: true
Explanation: We can obtain the string target from start by doing the following moves:
- Move the first piece one step to the left, start becomes equal to "L___R__R_".
- Move the last piece one step to the right, start becomes equal to "L___R___R".
- Move the second piece three steps to the right, start becomes equal to "L______RR".
Since it is possible to get the string target from start, we return true.

Example 2:

Input: start = "R_L_", target = "__LR"
Output: false
Explanation: The 'R' piece in the string start can move one step to the right to obtain "_RL_".
After that, no pieces can move anymore, so it is impossible to obtain the string target from start.

Example 3:

Input: start = "_R", target = "R_"
Output: false
Explanation: The piece in the string start can move only to the right, so it is impossible to obtain the string target from start.

 

Constraints:

• n == start.length == target.length
• 1 <= n <= 105
• start and target consist of the characters 'L', 'R', and '_'.

思考方式:

1. 由target String 反推。

2. 忽略"_", 從左到右每一個"L"或"R"都在給定的 start String 找到對應順序的"L"與"R", 如果順序不同就回傳false。

3. 最後檢查 start String 剩下的值是否都是"_"。

複雜度思考:

Time Complexity: O( N ) 

Space Complexity: O( x )

結果:

Runtime: 3 ms, Beats: 93.94%

Memory: 11.54 MB, Beats: 18.18%

Accepted

139 / 139 testcases passed

tendchen

submitted at Jun 17, 2025 21:58

Runtime

3ms

Beats93.94%

Analyze Complexity

Memory

11.54MB

Beats18.18%

Analyze Complexity

Code

C

bool canChange(char* start, char* target) {
    int str_len,i=0,j;
    int L_count=0,R_count=0;
    str_len=strlen(start);
    //printf("str_len=%d\n",str_len);
    bool return_val=true;

    for (j=0;j<str_len;j++)
    {
        if (target[j]=='L')
        {
            if (i==str_len)
            {
                //printf("(3)return false");
                return false;
            }
            //Search next L from start and the index i>=j
            for (;i<str_len;)
            {
                if (start[i]=='L')
                {
                    //i=i+1;
                    if (i<j)
                    {
                        //printf("(4)return false");
                        return false;
                    }
                    i=i+1;
                    break;
                }
                else if (start[i]=='R')
                {
                    //printf("(5)return false");
                    return false;
                }
                else
                {
                    i++;
                }
                if (i==str_len)
                {
                    //printf("(1)return false");
                    return false;
                }
            }
        }
        else if (target[j]=='R')
        {
            if (i==str_len)
            {
                //printf("(6)return false");
                return false;
            }
            //Search next R from start and the index i<=j
            for (;i<str_len;)
            {
                if (start[i]=='R')
                {
                    //i=i+1;
                    if (i>j)
                    {
                        //printf("(7)return false");
                        return false;
                    }
                    i=i+1;
                    break;
                }
                else if (start[i]=='L')
                {
                    //printf("(8)return false");
                    return false;
                }
                else
                {
                    i++;
                    //printf("i=%d",i);
                }
                if (i==str_len)
                {
                    //printf("(2)return false");
                    return false;
                }

            }
        }
    }
    //printf("i=%d\n",i);
    for (;i<str_len;)
    {
        if (start[i]!='_')
        {
            //printf("(9)return false");
            return false;
        }
        i++;
    }
    return return_val;
}