李恒道 发表于 2024-4-19 09:32:53

把str2整体插入到str1中的某个位置，形成最大的字典序前置推断

给定两个字符串str1和str2，想把str2整体插入到str1中的某个位置，形成最大的字典序，返回字典序最大的结果

大部分的都是直接推最优解法了
首先是把str插入str1，长度为N+M的字符串，将所有可能进行比较，得出一个字典序最大的字符串

但是为什么假设str1>=str2就可以直接跳过了？
我尝试查阅了很多资料，这部分都较为模糊
所以决定自己举例证明一下，不保证正确性

我们可以把字典序视为数字的比较，从而根据数字的连续性画出图，这样比较较为方便

首先假设str1>str2，为什么不需要在i位设置str2了？
可以得出图标
![图片.png](data/attachment/forum/202404/19/090623yoc48n2wcf1dzb81.png)
假设str2在k位不等了，则拼接出来的M+N字典序一定不如k+1位开始拼接的字符串大

则当大于时可以证明该字符串无效

当str1的部分=str2时
我们可以确定字典序相等，此时可以分为四种情况
![图片.png](data/attachment/forum/202404/19/090855y4h4wapu4s4phaop.png)
当第一种单调上时
如果加在任意位置，则一定会破坏上升的趋势，无法跟先全部上升最后拼接到最后的相比
![图片.png](data/attachment/forum/202404/19/091002qk3kzy85sacs11zs.png)
当第二种单调下时，放在i位没有任何帮助，一定会被单调下的过程中低于当前位的的前部分插入str2的M+N字符串替换掉，所以该情况无效
![图片.png](data/attachment/forum/202404/19/091823xpm87fol87n6nprv.png)
当第三种曲折时
![图片.png](data/attachment/forum/202404/19/092026wsw3eeqyyzydgqwp.png)
如果不在折点与前两种一样，如果在折点
这部分有一点绕，假设str2相同的字符是X(文中用圆形表示)
则错误情况直接在str1中X前插入str2
而正确情况则是在str1中X后的最近低于X的字符相邻插入
![图片.png](data/attachment/forum/202404/19/092237b0wwmw22qmql0mwm.png)
当第四种情况类似于第三种
但该两种最终得出的结论基本一致，所以不必在等于时插入，在第一个小于的字符开始插入可以等于相同作用
![图片.png](data/attachment/forum/202404/19/093051u4phzoapapgf5out.png)

根据以上四种情况总结可得出>=插入的多种情况都有最大解覆盖掉或有其他相同解，可以得出>=的情况下可以忽略


王一之 发表于 2024-4-19 09:41:20

猫耳 🐱

哥哥以后顺便贴下原题呗

李恒道 发表于 2024-4-19 09:42:44

王一之 发表于 2024-4-19 09:41
猫耳 🐱

哥哥以后顺便贴下原题呗

第一行就是原题描述

看着很短实际好几个坑
我到现在还没写出来

王一之 发表于 2024-4-19 09:43:19

李恒道 发表于 2024-4-19 09:42
第一行就是原题描述

看着很短实际好几个坑


链接捏？

李恒道 发表于 2024-4-19 09:44:31

王一之 发表于 2024-4-19 09:43
链接捏？

没leetcode
口口相传的题
我是在https://www.zhihu.com/question/452650138刷到的
页: [1]
查看完整版本: 把str2整体插入到str1中的某个位置，形成最大的字典序前置推断