0%

LeetCode题解777

发表于 更新于 分类于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

LeetCode题解

第777题，在LR字符串中交换相邻字符

在一个由 ‘L’ , ‘R’ 和 ‘X’ 三个字符组成的字符串（例如”RXXLRXRXL”）中进行移动操作。一次移动操作指用一个”LX”替换一个”XL”，或者用一个”XR”替换一个”RX”。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。

示例

1
2
3
4
5
6
7
8
9
输入: start = "RXXLRXRXL", end = "XRLXXRRLX"
输出: True
解释:
我们可以通过以下几步将start转换成end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

注意:

  1. 1 <= len(start) = len(end) <= 10000。
  2. start和end中的字符串仅限于'L', 'R'和'X'。

原题如上，代码如下：

python版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def canTransform(self, start, end):
        """
        :type start: str
        :type end: str
        :rtype: bool
        """
        if (len(start) != len(end)):
            return bool(0)
        n = len(start)
        sl = 0
        sr = 0
        el = 0
        er = 0
        for i in range(n):
            if start[i] == 'L':
                sl += 1
            if start[i] == 'R':
                sr += 1
            if end[i] == 'L':
                el += 1
            if end[i] == 'R':
                er += 1
            if (sl > el) | (sr < er):
                return bool(0)
        return bool((sl == el) & (sr == er) & (sl + sr < n))

19nlMF.png

c语言版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool canTransform(char * start, char * end){
    if(strlen(start) != strlen(end))
        return false;
    int i = 0 , n = strlen(start);
    int sl = 0,sr = 0,el = 0,er = 0;
    for(;i<n;i++){
        if(start[i]=='L')
            sl++;
        if(start[i]=='R')
            sr++;
        if(end[i]=='L')
            el++;
        if(end[i]=='R')
            er++;
        if((sl > el) || (sr < er))
            return false;
    }
    return (sl == el) && (sr == er) && (sl + sr < n);
}

19nYI1.png

做题原理：

注意：注意L只会向左移R只会向右移

  1. 先判等start和end的长度（肯定是相等的）。

  2. 记录下start和end中’L’和’R’的个数

  3. 同时遍历start和end

    ​ 19nZan.png

发现对’L’来说对于true的start到end：

1
2
sl <= el
sr >= er

因为’L’在变化的时候只会和它的左边对换位置，即对于start来说有可能会使 i 线右边的’L’对换到 i 线的左边，导致:

​ sl <= el

同理，因为’R’在变化的时候只会和它右边对换位置，即对于start来说有可能会使 i 线左边的’R’对换到 i 线的右边，导致:

​ sr >= er

则可以用(sl > el) || (sr < er)来判断false。

  1. 最后如若上述条件都满足，还要保证end是由start变化而来，即要满足(sl == el) && (sr == er) && (sl + sr < n)，则为true。(注意：sl+sr<n是因为还有’X’的存在)

    ​