leetcode

316. 去除重复字母

2020-02-22  本文已影响0人  十月里的男艺术家

题目

316. 去除重复字母

给定一个仅包含小写字母的字符串,去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

示例 1:

输入: "bcabc"
输出: "abc"

示例 2:

输入: "cbacdcbc"
输出: "acdb"

思路:

1、遍历字符串里的字符,如果读到的字符的 ASCII 值是升序,依次存到一个栈中;

2、如果读到的字符在栈中已经存在,这个字符我们不需要;

3、如果读到的 ASCII 值比栈顶元素严格小,看看栈顶元素在后面是否还会出现,如果还会出现,则舍弃栈顶元素,而选择后出现的那个字符,这样得到的字典序更小。

代码:

import "bytes"

func removeDuplicateLetters(s string) string {
    b := []byte(s)
    var r []byte
    for i, c := range b {
        if len(r) == 0 {
            r = append(r, c)
            continue
        }
        if bytes.IndexByte(r, c) != -1 {
            continue
        }

        for len(r) > 0 && c < r[len(r)-1] && bytes.IndexByte(b[i+1:], r[len(r)-1]) != -1 {
            r = r[:len(r)-1]
        }
        r = append(r, c)
    }
    return string(r)
}
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        stack = ''
        last_index = {c:i for i, c in enumerate(s)}
        for i, c in enumerate(s):
            if c not in stack:
                while c < stack[-1:] and i < last_index[stack[-1]]:
                    stack = stack[:-1]
                stack += c
        return stack
        
上一篇 下一篇

猜你喜欢

热点阅读