如何获得最小的字典顺序？ [英] How to get the smallest in lexicographical order?

问题描述

我正在做leetcode练习

I am doing a leetcode exercise

https://leetcode.com/problems/remove-duplicate-letters/

问题是：

# 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"

我不太确定词典中最小的是什么订单以及为什么给出 cbacdcbc，那么答案将是 acdb

I am not quite sure about what is the smallest in lexicographical order and why Given "cbacdcbc" then the answer would be "acdb"

感谢您提前给出答案：）

Thanks for the answer in advance :)

推荐答案

最小词典顺序是字符串 s 小于 t 的顺序关系，给定 s （ s ₁ ）的首字符小于 t （ t ₁ ），或者等价于第二个字符，等等。

The smallest lexicographical order is an order relation where string s is smaller than t, given the first character of s (s₁) is smaller than the first character of t (t₁), or in case they are equivalent, the second character, etc.

所以 aaabbb 小于 aaac ，因为尽管前三个字符相等，但第四个字符 b 小于第四个字符 c 。

So aaabbb is smaller than aaac because although the first three characters are equal, the fourth character b is smaller than the fourth character c.

对于 cbacdcbc ，由于 b 和 c 是重复项，您可以决定删除哪些重复项。结果是：

For cbacdcbc, there are several options, since b and c are duplicates, you can decided which duplicates to remove. This results in:

cbacdcbc = adbc
cbacdcbc = adcb
cbacdcbc = badc
cbacdcbc = badc
...

因为 adbc < adcb ，因此您不能简单地想到一个突然出现的答案。

since adbc < adcb, you cannot thus simply answer with the first answer that pops into your mind.

这篇关于如何获得最小的字典顺序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！