要在所有排列中尝试拼接再删字符并选最小,直接暴力枚举所有 n! 种排列,每种排列拼接后长度最多 L≤80,再枚举删除位置,复杂度约为 O(n!×L2)。
可以优化:对于给定字符序列 S,要删除一个字符后使得结果字典序最小,只需找到第一个使得 S[i]>S[i+1] 的位置 i,删除 S[i];若不存在这样的下降点,则删除末尾字符。该贪心策略可在线性时间 O(L) 内完成。
因此总体流程:
对于给定的长度为n,仅由字符串构成的数组{a1,a2,...an}每一个字符串都仅由小写字母构成。
你需要将全部字符串按照任意顺序拼按成一整个字符串(但是不改变每个字符串内部的顺序),随后恰好删除其中的一个字符