网站推广目标什么意思,wordpress设计页面教程,长沙 外贸网站建设公司,个人成立公司怎么做企业网站【每日一题】2337. 移动片段得到字符串 2337. 移动片段得到字符串题目描述解题思路 2337. 移动片段得到字符串
题目描述
给你两个字符串 start 和 target #xff0c;长度均为 n 。每个字符串 仅 由字符 ‘L’、‘R’ 和 ‘_’ 组成#xff0c;其中#xff1a;
字符 ‘L’… 【每日一题】2337. 移动片段得到字符串 2337. 移动片段得到字符串题目描述解题思路 2337. 移动片段得到字符串
题目描述
给你两个字符串 start 和 target 长度均为 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 start.length target.length 1 n 105 start 和 target 由字符 ‘L’、‘R’ 和 ‘_’ 组成
解题思路
思路最直观的思路是条件一是start和target中的L和R的相对顺序是一致的条件二是在相对顺序一致的情况下L只能左移R只能右移那么该如何实现呢对于条件一分别将start和target中的_去掉然后再判断是否相等如果相等则满足条件一对于条件二分别枚举对应位置的L和R如果L满足ij且R满足ij则满足条件二。
class Solution {
public:bool canChange(string start, string target) {// 条件一 start和target中L和R的相对顺序不变auto sstart,ttarget;// remove(begin(),end(),c) 移除[b,e)区间内的c 并将c后移 // 字符串长度不变 前面为移除后的字符串 后面为原始字符串s.erase(remove(s.begin(),s.end(),_),s.end());// s.erase(begin(),end()) 移除[b,e)区间内字符串t.erase(remove(t.begin(),t.end(),_),t.end());// 条件一判断if(s!t) return false;// 条件二 start中的L只能左移 R只能右移int nstart.length();// 可以使用双指针实现int i0,j0;while(injn){while(start[i]_)i;while(target[j]_)j;// 条件二判断if((start[i]Lij)||(start[i]Rij))return false;else{i;j;}}return true;}
};总结先有思路再有实现。先库函数再自己写。remove(begin(),end(),c) 移除[b,e)区间内的c并将c后移字符串长度不变前面为移除后的字符串后面为原始字符串比如原始字符串s为_L__R__R_“使用remove后得到LRR_R__R_”。s.erase(begin(),end()) 移除[b,e)区间内字符串。
