кратчайший дайджест строки - PullRequest
3 голосов
/ 03 марта 2010

[Описание] По заданной строке типа char найдите кратчайший дайджест, который определяется как: кратчайшая подстрока, содержащая все символы в исходной строке.

[Пример]

A = "aaabedacd"

B = "Bedac" является ответом.

[Мое решение]

  1. Определить целочисленную таблицу с 256 элементами, которая используется для записи времени появления для каждого вида символов в текущей подстроке.

  2. Сканирование всей строки, статистика общего количества символов в данной строке с использованием таблицы выше.

  3. Используйте два указателя, начало, конец, которые изначально указывают на начало и (начало + 1) данной строки. Текущий тип символов: 1.

  4. Расширять подстроку [start, end) в конце, пока она не будет содержать все виды символов. Обновите кратчайший дайджест, если это возможно.

  5. Подстрока контракта [начало, конец] в начале на один символ каждый раз, попробуйте восстановить ее свойство дайджеста, если необходимо, к шагу 4.

Стоимость времени O (n), а стоимость дополнительного места постоянна.

Есть ли лучшее решение без лишних пробелов?

Ответы [ 3 ]

2 голосов
/ 03 марта 2010

Я не думаю, что ваш алгоритм правильный. Рассмотрим строку: «baaabedacdc». Правильный ответ по-прежнему "bedac", но ваш алгоритм будет продвигать указатель начала вперед до тех пор, пока не найдет "e" (единственный символ с числом вхождений 1), а затем указатель конца назад, пока не найдет "e" (единственный символ с числом вхождений 1), для результата "e".

Возможно, я неправильно понял алгоритм.

2 голосов
/ 03 марта 2010

Это работает очень плохо, если учесть тот факт, что символы на самом деле не ограничены 256; в Юникоде ближе к 2 ^ 32 кодам; и если вы попробуете то, что планируете, для строки UTF-8, она взорвется. В большом смысле.

Лучшим подходом было бы использовать алгоритм дайджеста, такой как MD5 или FNV, или делать то, что вы делаете, а вместо этого связанный список разреженный массив; добавление кодовых точек символов по мере их появления и последующее объединение кодовых точек с преобразованием, скажем, в UTF-8 по ходу работы.

EDIT:

Контрпример: "På japansk heter regn '雨'."

0 голосов
/ 25 марта 2010

Почему бы не использовать более простой алгоритм для этого вопроса, может быть не самый эффективный по времени, но он работает;):

шаг 1. (Предполагая, что мы имеем дело с набором символов из 26 алфавитов), создайте логический массив размера 26, просмотрите строку и проверьте логическое значение, соответствующее символу. Например, установите elem [0] = true, когда вы сталкиваетесь с a, elem [1] = true, когда вы сталкиваетесь с b и т. Д.

шаг 2. создайте строку, используя символы, где elem [x] = true. Итак, строка для этого случая будет "abcde" и ее длина = 5.

шаг 3. второй раз пройти по заданной строке, извлекая подстроки длиной 5, сортируя их в порядке возрастания и сопоставляя их со строкой из шага 2.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...