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

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

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

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

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

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

首先假设str1>str2，为什么不需要在i位设置str2了？
可以得出图标
图片.png
假设str2在k位不等了，则拼接出来的M+N字典序一定不如k+1位开始拼接的字符串大

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

当str1的部分=str2时
我们可以确定字典序相等，此时可以分为四种情况
图片.png
当第一种单调上时
如果加在任意位置，则一定会破坏上升的趋势，无法跟先全部上升最后拼接到最后的相比

当第二种单调下时，放在i位没有任何帮助，一定会被单调下的过程中低于当前位的的前部分插入str2的M+N字符串替换掉，所以该情况无效
图片.png
当第三种曲折时

如果不在折点与前两种一样，如果在折点
这部分有一点绕，假设str2相同的字符是X(文中用圆形表示)
则错误情况直接在str1中X前插入str2
而正确情况则是在str1中X后的最近低于X的字符相邻插入

当第四种情况类似于第三种
但该两种最终得出的结论基本一致，所以不必在等于时插入，在第一个小于的字符开始插入可以等于相同作用
图片.png