html教学网站,网站 cms,南昌微信网站建设,深圳 微网站题目链接 Leetcode.2337 移动片段得到字符串 rating : 1693 题目描述
给你两个字符串 start 和 target #xff0c;长度均为 n n n 。每个字符串 仅 由字符 L、R 和 _ 组成#xff0c;其中#xff1a;
字符 L 和 R 表示片段#xff0c;其中片段 L 只有在其左侧直接存在一…题目链接 Leetcode.2337 移动片段得到字符串 rating : 1693 题目描述
给你两个字符串 start 和 target 长度均为 n n n 。每个字符串 仅 由字符 L、R 和 _ 组成其中
字符 L 和 R 表示片段其中片段 L 只有在其左侧直接存在一个 空位 时才能向 左 移动而片段 R 只有在其右侧直接存在一个 空位 时才能向 右 移动。字符 _ 表示可以被 任意 L 或 R 片段占据的空位。
如果在移动字符串 start 中的片段任意次之后可以得到字符串 target 返回 true 否则返回 false 。
示例 1 输入start “L__R__R”, target “L______RR” 输出true 解释可以从字符串 start 获得 target 需要进行下面的移动 将第一个片段向左移动一步字符串现在变为 “L___R__R_” 。将最后一个片段向右移动一步字符串现在变为 “L___R___R” 。将第二个片段向右移动三步字符串现在变为 “L______RR” 。 可以从字符串 start 得到 target 所以返回 true 。 示例 2 输入start “R_L_”, target “__LR” 输出false 解释字符串 start 中的 ‘R’ 片段可以向右移动一步得到 “RL” 。 但是在这一步之后不存在可以移动的片段所以无法从字符串 start 得到 target 。 示例 3 输入start “R, target R” 输出false 解释字符串 start 中的片段只能向右移动所以无法从字符串 start 得到 target 。 提示 n s t a r t . l e n g t h t a r g e t . l e n g t h n start.length target.length nstart.lengthtarget.length 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105start 和 target 由字符 L、R 和 _ 组成
解法双指针
如果 start 能够转成 target说明把 start 和 target 中间的 _ 都去掉二者还是相同的否则不能进行转换。
接下来用两个指针 i i i 和 j j j 分别指向start 和 target 的起始位置开始遍历
如果 start[i] _ 或者 target[j] _都跳过如果 start[i] L并且 i j i j ij由于 L不能向 右 移动所以此时不能转换直接返回 false如果 start[i] R并且 i j i j ij由于 R不能向 左 移动所以此时不能转换直接返回 false
最后没问题就返回 true
时间复杂度 O ( n ) O(n) O(n)
C代码
class Solution {
public:bool canChange(string start, string target) {auto s start , t target;s.erase(remove(s.begin(),s.end(),_),s.end());t.erase(remove(t.begin(),t.end(),_),t.end());if(s ! t) return false;int n start.size();for(int i 0,j 0;i n;i){if(start[i] _) continue;while(j n target[j] _) j;if(i ! j){if(start[i] L i j) return false;else if(start[i] R i j) return false;}j;} return true; }
};
