Как получить самый маленький в лексикографическом порядке?

Question

Я делаю leetcode упражнения

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" 

Я не совсем уверен, что what is the smallest in lexicographical order и почему Учитывая "cbacdcbc", то ответ будет "AcDb"

Спасибо за ответ заранее

Answer 1

Самый маленький Лексикографическое порядок есть отношение порядка, где строка с меньше т, учитывая первый символ с (с) меньше, чем первый символ т (т), или в случае, если они эквивалентны, второй символ и т.д.

Так aaabbb является Smalle r, чем aaac, потому что хотя первые три символа равны, четвертый символ b меньше четвертого символа c.

Для cbacdcbc существует несколько вариантов, поскольку b и c являются дубликатами, вы можете решить, какие дубликаты удалить. Это приводит к:

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

< так adbcadcb, вы не можете, таким образом, просто ответить с первым ответом, который появляется в вашем уме.

Answer 2

the smallest in lexicographical order - ваш ответ должен быть подпоследовательностью исходной строки, содержащей один экземпляр каждого символа.
Если существует много таких подпоследовательностей (bca, bac, cab, abc для первого примера), верните наименьший из них, сравнив их как строки (рассмотрите порядок строк в словаре).

why Given "bcabc" then the answer would be "acdb"
Вы смущены два разных примера

Answer 3

Там, кажется, какое-то недоразумение; в примере указано, что для входа bcabc ожидаемый выход должен быть abc, а не acdb, что относится к входу cbacdcbc.

Answer 4

ясно, требуемый выход должен содержать только букву один раз. Теперь, из того, что я понимаю, вы должны выбрать буквы таким образом, чтобы дать вам лучший порядок, когда самые левые буквы приходят раньше (abc? Ascii?) Теперь вы спросите, почему «acdb», а не «нет», ABCD». я думаю, что вы не берете первый «cb», так как вам больше c и b позже, но вам нужно взять «a», так как теперь есть только один. то вы должны взять c, потому что больше нет «d» после следующего b. вот почему вы берете c, а затем d, потому что не более того.

Короче говоря, вы хотите взять его с лучшим лексикографическим порядком от низкого до высокого, но убедитесь, что вы берете все буквы, итерации по входной строке.

Answer 5

сравнения строк обычно можно сделать 2-мя способами:

• сравнения для первого непревзойденную письма (так называемый лексикографическом), например aaccccccменьше чем ab, потому что на второй позиции b были выполнены (и a < b).
• сравнение длина строки первая и более короткая строка обрабатываются как меньше. Если длина строк равна, то примените лексикографию.

Второй может быть быстрее, если известна длина строк.

Вы вопрос содержит небольшую ошибку:

why Given "bcabc" then the answer would be "acdb"

Хотя происхождение было: "Учитывая "bcabc" Возвращение "ABC"". Имеет смысл, что abc должен быть возвращен вместо bca

Answer 6

Вы не можете изменить порядок символов. Вы можете выбрать, какое событие следует удалить в случае дублированных символов.

bcabc 

Мы можем удалить либо первый b или второй b, мы можем удалить либо первый c или второй c. Все вместе четыре выхода:

..abc 
.cab. 
b.a.c 
bca.. 

Сортировать эти четыре выхода лексикографический (в алфавитном порядке):

abc 
bac 
bca 
cab 

и возьмите первые один:

abc