- tags: LeetCode
移除小写字母中重复的字母，让所有字母都只出现一次，并且结果是所有结果中按照字典序排序最小的那个。
Example 1
- Input: “bcabc”
- Output: “abc”
Example 2
- Input: “cbacdcbc”
- Output: “acdb”
解法之一:
- 通过一个数组对每一个出现的字母进行计数
- 遍历每一个字母放入栈，并将该字母的计数减 1
- 查看栈底的字母有没有比当前字母大且该字母的计数不为 0 的（有比当前更小的字典序），从栈底弹出该字母
func removeDuplicateLetters(s string) string {
var countOfEachLetter [26]int
var visited [26]bool
stack := make([]byte, 0)
stackBottom := 0
bytesArr := []byte(s)
for _, c := range bytesArr {
countOfEachLetter[getIndex(c)]++
}
for _, c := range bytesArr {
index := getIndex(c)
countOfEachLetter[index]--
if visited[index] {
continue
}
// countOfEachLetter[getIndex(stack[stackBottom])] > 0 后面还有该字符
for len(stack[stackBottom:]) > 0 && stack[stackBottom] > c && countOfEachLetter[getIndex(stack[stackBottom])] > 0 {
// 标记为未访问用于后面的字符加入结果
visited[getIndex(stack[stackBottom])] = false
// 移动栈底
stackBottom++
}
// 加入到结果栈
stack = append(stack, c)
visited[index] = true
}
return string(stack[stackBottom:])
}
func getIndex(b byte) int {
return int(b - 'a')
}
通过上面解法遇到如下错误：
- testcase: ‘“bbcaac”’
- answer: “bca”
- expected_answer: “bac”
经过一番排查不应该从栈底查找，应该从栈顶开始，通过的代码如下：
func removeDuplicateLetters(s string) string {
var countOfEachLetter [26]int
var visited [26]bool
st := &stack{}
bytesArr := []byte(s)
for _, c := range bytesArr {
countOfEachLetter[getIndex(c)]++
}
for _, c := range bytesArr {
index := getIndex(c)
countOfEachLetter[index]--
if visited[index] {
continue
}
// countOfEachLetter[getIndex(st.topChar())] > 0 后面还有该字符
for !st.empty() && st.topChar() > c && countOfEachLetter[getIndex(st.topChar())] > 0 {
// 标记为未访问用于后面的字符加入结果
visited[getIndex(st.pop())] = false
}
// 加入到结果栈
st.push(c)
visited[index] = true
}
return st.String()
}
func getIndex(b byte) int {
return int(b - 'a')
}
type stack struct {
top *stackItem
bottom *stackItem
}
type stackItem struct {
prev *stackItem
next *stackItem
c byte
}
func (s *stack) topChar() byte {
return s.top.c
}
// 从栈顶弹出
func (s *stack) pop() byte {
top := s.top
s.top = s.top.prev
if top == s.bottom {
s.bottom = s.top
}
return top.c
}
func (s *stack) push(c byte) {
new := &stackItem{
prev: s.top,
c: c,
}
if s.bottom == nil {
s.bottom = new
}
if s.top == nil {
s.top = new
} else {
s.top.next = new
s.top = new
}
}
func (s *stack) empty() bool {
return s.top == nil
}
func (s *stack) String() string {
buf := make([]byte, 0, 10)
current := s.bottom
for current != nil {
buf = append(buf, current.c)
current = current.next
}
return string(buf)
}