leetcode刷题指南之RemoveDuplicateLetters

编辑 | 刘凯旋

公众号 | 转载自 【编程与算法之美】

1.题目分析

给定一个字符串,删去重复字母使得每个字母只剩一个,并且字典序最小。

2.解题思路

最暴力的方法就是用dfs去搜索,记录哪些字母还没有出现,这个的复杂度是O(26!)的 ,显然不行。

暴力的做法只考虑了前一个条件,却没有考虑字典序最小这个也很关键的条件。想一下,字典序最小的情况,最优的肯定是字母较小的尽量靠前,字母大的尽量靠后。然而这个尽量,到底是什么程度呢?

考虑一个例子:

bcac,对于字母a来说,它显然不可能出现在首位,因为那意味着要把前面的bc删掉,而a的后面就不可能再有b了,而它却可以出现在c的前面,因为把它前面的c删掉之后,它的后面还有一个c。

因此,整体的算法就出来了:

我们一位一位处理字符串,假设处理到了第i位,并且已经得到当前最优的字符串s,如果第i位已经出现在s中,那么就没必要保留这一位了。

如果没有,考虑s的最后一个字母,如果它比最后第i位小,并且在第i位之后还出现了,那么就删掉,直到s为空或者s的最后一个字母不满足条件,把第i位放到最后。

举样例跑一遍:

cbacdcbc. 初始s为空。

i=0,s=c i=1,此时可以删掉c,s=b i=2,此时b可以删,s=a i=3,s=aci=4,此时s=acd i=5,此时s=acd i=6,此时s=acdb i=7,此时s=acdb

3.代码示例

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181104B00PTI00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券