Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example:
Given "bcabc"
Return "abc"
Given "cbacdcbc"
Return "acdb"
[leetcode 316] Remove Duplicate Letters
这道题是一道hard难度的题目,如果没有头绪的话,解起来还是比较复杂的,思路倒是很清楚,就是找到第一个不能删的字符,然后从起始字符到该字符串之间找到一个最小的字符作为结果字符串的第一个字符,然后对该字符后面的字符串继续上述操作。
这里给出leetcode上两种解法,一个是递归,一个是使用for循环。
递归方法
这个递归还是比较清楚的,每次统计字符出现的个数,然后遍历,对应的字符个数减减,直到出现为0。。。
for循环
详细说明参见:Easy to understand iterative Java solution
具体的,先找到每个字符串最后一次出现的下标,然后对于最小的下标,找结果字符串前一个固定的下标到该最小下标之间的字符串中最小的字符作为当前被添加到结果字符串的字符。
还是举个例子吧:
比如cbacdcbc
,对应的c-7,b-6,a-2,d-4
,然后找到a-2
,这样从第0个字符到第2个字符之间最小的字符是a
,那么结果字符串就变为a
,然后继续找到d-4
,这里从结果字符串的前一个字符对应的下标的后一个下标对应的字符到第4个字符之间最小的字符,是c
,这样结果字符串就变为ac
,继续我们发现d-4
并没有走到,那么继续从结果字符串的前一个字符对应的下标的后一个下标对应的字符到第4个字符之间最小的字符,是d
,这样结果字符串变为acd
,继续找到b-6
,继续从结果字符串的前一个字符对应的下标的后一个下标对应的字符到第6个字符之间最小的字符,是b
,结果字符串变为acdb
,然后找到c-7
,由于c已经出现了,就直接跳过…
代码如下: