leetcode 87. 扰乱字符串

devtools/2025/1/15 21:36:55/

题目:87. 扰乱字符串 - 力扣(LeetCode)

dfs+状态记录。

  • dfs:以两个字符串 [a1,a2,a3,a4] 和 [b1,b2,b3,b4]为例,可以往下搜以下几种情况,一种情况为true就能返回true
    • F([a1],[b1]) && F([a2,a3,a4],[b2,b3,b4])
    • F([a1],[b4]) && F([a2,a3,a4],[b1,b2,b3])
    • F([a1,a2],[b1,b2]) && F([a3,a4],[b3,b4])
    • F([a1,a2],[b3,b4]) && F([a3,a4],[b1,b2])
    • F([a1,a2,a3],[b1,b2,b3]) && F([a4],[b4])
    • F([a1,a2,a3],[b2,b3,a4]) && F([a4],[b1])
  • 状态记录:记录两个字符串a和b的起始位置和长度,可以用一个三维数组表示 f[ia][ib][length] ,看数据规模只有 30,嫌麻烦直接用了一维数组 f[ia * 10000 + ib * 100 + length]
    class Solution {
    public:bool F(const char* a, const char* b, int ia, int ib, int len, uint8_t* f) {if (len == 1 && a[ia] == b[ib]) {return true;}int idx = ia * 10000 + ib * 100 + len;if (f[idx]) {return f[idx] == 1;}f[idx] = 1;for (int i = 0; i < len; i++) {if (a[ia + i] != b[ib + i]) {f[idx] = 2;break;}}if (f[idx] == 1) {return true;}for (int i = 1; i < len; i++) {if (F(a, b, ia, ib, i, f) && F(a, b, ia + i, ib + i, len - i, f)) {f[idx] = 1;break;}if (F(a, b, ia, ib + len - i, i, f) && F(a, b, ia + i, ib, len - i, f)) {f[idx] = 1;break;}}return f[idx] == 1;}bool isScramble(string s1, string s2) {const char* a = s1.c_str();const char* b = s2.c_str();int n = (int) s1.length();uint8_t* f = new uint8_t[400000];memset(f, 0, 400000);return F(a, b, 0, 0, n, f);}
    };


http://www.ppmy.cn/devtools/150768.html

相关文章

《自动驾驶与机器人中的SLAM技术》ch2:基础数学知识

目录 2.1 几何学 向量的内积和外积 旋转矩阵 旋转向量 四元数 李群和李代数 SO(3)上的 BCH 线性近似式 2.2 运动学 李群视角下的运动学 SO(3) t 上的运动学 线速度和加速度 扰动模型和雅可比矩阵 典型算例&#xff1a;对向量进行旋转 典型算例&#xff1a;旋转的复合 2.3 …

STM32 C++编程,怎样使用printf函数从串口输出中文字符

在STM32 C编程中&#xff0c;使用printf函数从串口输出中文字符是可行的&#xff0c;但需要注意字符编码的问题。由于STM32的默认编码是ASCII&#xff0c;而中文字符通常属于Unicode编码&#xff08;如UTF-8或GB2312&#xff09;&#xff0c;因此需要对字符编码进行转换和处理。…

探索图像编辑的无限可能——Adobe Photoshop全解析

文章目录 前言一、PS的历史二、PS的应用场景三、PS的功能及工具用法四、图层的概念五、调整与滤镜六、创建蒙版七、绘制形状与路径八、实战练习结语 前言 在当今数字化的世界里&#xff0c;视觉内容无处不在&#xff0c;而创建和编辑这些内容的能力已经成为许多行业的核心技能…

Codeforces Round 976 (Div. 2) and Divide By Zero 9.0(A-E)

链接&#xff1a;Dashboard - Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 - Codeforces A. Find Minimum Operations 思路 可以观察发现这里有个进制的思想&#xff0c;转换为k进制把每位数相加即可 代码 void solve(){int n,k;cin>>n>>k;if(k1){…

浏览器处理文件,前端对二进制数可以使用的原生API,非xlsx等插件

参考帖子1&#xff1a;https://www.cnblogs.com/wanghuizhao/p/16534435.html 参考帖子2&#xff1a;https://blog.csdn.net/2301_77404895/article/details/138278262 参考帖子3&#xff1a;有企鹅的推广https://cloud.tencent.com/developer/information/%E6%9D%A5%E8%87%AAu…

ros2笔记-7.1 机器人导航介绍

7.1 机器人导航介绍 7.1.1 同步定位与地图构建 想要导航&#xff0c;就是要确定当前位置跟目标位置。确定位置就是定位问题。 手机的卫星导航在室内 受屏蔽&#xff0c;需要其他传感器获取位置信息。 利用6.5 章节的仿真&#xff0c;打开并运行 会发现轨迹跟障碍物都被记录…

docker镜像加速器自动换源开源项目dkTurbo——筑梦之路

docker run运行 # 每一项参数都是必要的&#xff0c;请勿随意修改除环境变量以外的参数 docker run --rm \--namedkturbo \-v /etc/docker:/etc/docker \-v /opt:/opt \-e MODEregistry \-e REGISTRYauto \--networkbridge \--pidhost \--privileged \registry.cn-shenzhen.al…

【Ubuntu与Linux操作系统:九、Shell编程】

第9章 Shell编程 9.1 Shell编程基本步骤 Shell编程是一种通过编写脚本文件&#xff0c;使用Shell解释器执行批处理任务的方法。基本步骤如下&#xff1a; 1. 确定需求 在编写脚本之前&#xff0c;明确要实现的功能&#xff0c;例如文件备份、日志分析或自动化部署等。需求的清…