LeetCode 2337. Move Pieces to Obtain a String【字符串,双指针】1693

这篇具有很好参考价值的文章主要介绍了LeetCode 2337. Move Pieces to Obtain a String【字符串,双指针】1693。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你两个字符串 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 <= 10^5
  • start 和 target 由字符 'L''R' 和 '_' 组成

解法 双指针

首先,无论怎么移动,由于 L L L R R R 无法互相穿过对方,那么去掉 _ 后的剩余字符应该是相同的,否则返回 f a l s e false false 。然后用双指针从左向右遍历 start \textit{start} start target \textit{target} target ,分类讨论:

  • 如果当前字符为 L L L i < j i<j i<j ,由于 L L L 由于无法向右移动,返回 f a l s e false false
  • 如果当前字符为 R R R i > j i>j i>j ,由于 R R R 由于无法向左移动,返回 f a l s e false false
  • 遍历完,若中途没有返回 f a l s e false false 就返回 t r u e true true
class Solution {
public:
    bool canChange(string start, string target) {
        int n = start.size();
        int i = 0;
        for (int j = 0; j < n; ++j) {
            if (target[j] == '_') continue;
            while (i < n && start[i] == '_') ++i;
            if (i == n || 
                start[i] != target[j] || // 当前字符不同
                i != j && (start[i] == 'L') == (i < j)) 
                return false; // 顺序不符合
            ++i; 
        }
        while (i < n)
            if (start[i++] != '_') return false;
        return true;
    }
};

复杂度分析:文章来源地址https://www.toymoban.com/news/detail-663384.html

  • 时间复杂度: O ( n ) \mathcal{O}(n) O(n) ,其中 n n n start \textit{start} start 的长度。
  • 空间复杂度: O ( 1 ) \mathcal{O}(1) O(1)

到了这里,关于LeetCode 2337. Move Pieces to Obtain a String【字符串,双指针】1693的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Python小技巧】df转字符串用df.to_string(),字符串转换回DataFrame怎么办?

    平常我们使用pandas,一般使用的是DataFrame和Series,但个别交换数据的时候,只能使用字符串,我们需要将df转为字符串输出。但交换完的数据,我们又需要将字符串再转回DataFrame格式,这个怎么办呢? 下文我们就来看看,如何处理?文中df代表DataFrame数据。 df转为字符串 dfs

    2024年01月24日
    浏览(45)
  • LeetCode 2496. Maximum Value of a String in an Array【字符串,数组】简单

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月11日
    浏览(55)
  • 字符串分割(split),将字符串按照指定字符进行分割。split(String regex)和split(String regex, int limit)

    一、 split(String regex) 字符串分割,将字符串按照指定字符进行分割,返回的是一个字符串数组。 原理:参数名称是 regex 表示的是以某个字符串进行字符分割。 实例1:根据空格切割 输出结果: 实例2:根据特殊字符进行“.”分割 输出结果: 二、 split(String regex, int limit) 字符

    2024年02月11日
    浏览(50)
  • String字符串

    直接创建 代码简单,节约内存 使用new创建 有new就会开辟一个新的小空间,地址值不同不会复用浪费空间 案例:用户登录 遍历字符串 统计字符个数 拼接字符串 字符串反转 金额转换 手机号屏蔽 敏感词替换 使用场景:1.字符串拼接。2、字符串反转 常用方法练习 对称字符串

    2024年02月16日
    浏览(51)
  • String(字符串)

    java.lang.String类代表字符串,Java程序中的所有字符串文字(例如“abc”)都为此类的对象。 字符串的内容是不会发生改变的,它的对象在创建后不能被更改。 String是Java定义好的一个类。定义在java.lang包中,所以使用的时候不需要导包。 Java程序中的所有字符串文字都被实为此

    2024年02月13日
    浏览(45)
  • C# 字符串(String)

    C#基础学习入门系列- C# 字符串(String) C#字符串(String)是一种不可变的序列字符。任何对字符串的操作都会返回一个新的字符串。字符串在C#中是一个引用类型,使用System.String类表示。 字符串可以通过使用双引号或者@符号来创建。双引号用于创建普通字符串 ,例如: @符

    2024年01月21日
    浏览(55)
  • redis—String字符串

    目录 前言 1.字符串数据类型 2.常见命令 3.典型应用场景 字符串类型是Redis最基础的数据类型,关于字符串需要特别注意: 1)首先Redis中所有的键的类型都是字符串类型,而且其他几种数据结构也都是在字符串类似基础.上构建的,例如列表和集合的 元素类型是字符串类型,所以

    2024年02月02日
    浏览(47)
  • rust 字符串(String)详解

    rust中的 String ,是一个非常常用的 crate ,它的底层涉及到了rust中的所有权概念,不过这不是本章的内容,如果对rust所有权概念感兴趣的,可以查看另一篇文章:rust所有权 本文的目的还是介绍 String 的基本用法,以及有哪些常用的函数可以使用 字符串,也就是由一系列字符

    2024年02月03日
    浏览(44)
  • 6.string字符串的比较

    比较结果是真或假, 比较:字符串是1和1比较 然后9和2 比较 大后面就不用比了 对应字符比他大就行了。 结果:如果这个是符合比较运算符的就返回真。反之假 跟具不同的目的选择不同的运算符, 结果只有真和假,运算符不是最后的结果。 总结:如果这个是符合比较运算符

    2024年02月15日
    浏览(39)
  • 【string题解 C++】字符串相乘 | 翻转字符串III:翻转单词

    目录 字符串相乘 题面 错误记录 Way1 拆分成“先乘后加” 思路 实现 时空复杂度分析 反思 Way2 用数组 思路 实现 时空复杂度分析 翻转字符串III:翻转字符串中的单词 题面 错误记录 思路1 遍历找单词 实现 思路2 暴力解法 实现 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平

    2024年02月07日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包