Лучший способ / алгоритм, чтобы узнать, состоит ли строка только из данного набора символов

Question

Меня спросили об этом в интервью, Если вам нужно выяснить, состоит ли строка только из заданного набора символов. Например, пусть набор строк будет всеми строками свыше {0,1,2,3,4,5,6,7,8,9}, то есть всеми «числовыми» строками. Среди этого, если набор строк более {3,8,5} является только допустимым, как мне проверить, состоит ли строка только из допустимых символов. Скажи:

Input 8888338385
     Output VALID
Input 887837348234 
Output : Invalid

Я предложил только грубую силу, которая требовала проверки каждого символа в данной строке по списку недопустимых символов. Если какой-либо из символов был недействительным, я бы пропустил проверку всех остальных символов и отобразил бы сообщение об ошибке. Однако, как предложено здесь , могут быть лучшие алгоритмы. Пожалуйста, помогите.

Answer 1

РЕДАКТИРОВАТЬ: Спасибо Люку Турэю за огромное улучшение оригинального алгоритма.

Создать массив a[10] логических значений. Для каждой ожидаемой цифры e установите a[e] = true.

Теперь для каждой цифры d в вашем входе, проверьте, является ли a[d] истиной. Если это не так, верните false. Если все они успешны, верните true.

Вы можете обобщить это для всех символов ASCII с массивом из 256 элементов.

Если ваша входная строка имеет длину N, ваша строка сравнения имеет длину M, а количество букв в вашем алфавите равно A, то сложность составляет O (N + M) (для сканирования двух строк) плюс O (A ) (для инициализации логического массива). Поэтому, если длина вашей строки не превышает размер алфавита или превышает его, это может быть неоптимальным.

Стоит отметить, что в отношении превосходного сравнения производительности Никласа Баумстарка, наши два решения фактически одинаковы. Построенный здесь логический массив идентичен таблице переходов, которую вы строите в двух состояниях DFA , принимающей [c ₁ c ₂ ...] *. Думаю, единственное отличие состоит в том, что реализация Java, будучи гораздо более общей, несет в себе гораздо больше накладных расходов.

Answer 2

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: Вопреки моим предположениям, Java, похоже, сосет при оптимизации используемого здесь регулярного выражения, что приводит к неработающему коду.Даже регулярные выражения Javascript, кажется, быстрее, чем это.Тест также показывает, что решение Ника действительно быстрое.

Это определенно задача для регулярного выражения.В Java:

public boolean isValidString(String str) {
  return str.matches("[358]*");
}

Это должен быть O(n) худший случай, и он не может быть лучше, чем это, потому что на каждый символ нужно смотреть.

Если производительность критична, вы, вероятно, захотите кэшировать предварительно скомпилированное сопоставление с шаблоном:

import java.util.regex.Pattern;

public class Matcher {
  private Pattern pattern;

  public Matcher() {
    this.pattern = Pattern.compile("[358]*");
  }

  public isValid(String str) {
    return pattern.matcher(str).matches();
  }
}

Answer 3

для c или c ++, вы можете сделать что-то вроде этого:

const char* haystack = "8888338385";
const char* filter = "385";

if (strlen(haystack) != strspn(haystack, filter))
{
  // oops - haystack contains more characters...
}

Эквивалентные std::string функции существуют для c ++ (std::string::find_first_not_of)

РЕДАКТИРОВАТЬ: Я понимаю, что это обман, но в этом вопросе нет ничего, что препятствует этому.

Answer 4

Вы можете использовать карту для каждого символа в разрешенном наборе (если алфавит имеет ограниченный диапазон) и проверять непосредственно для каждого символа в строках, которые вы проверяете, присутствует ли он на карте. таким образом, только O (N), где N - длина строки, а не O (N * M), где M - набор разрешенных символов. Если алфавит имеет большой масштаб, для хранения разрешенных символов можно использовать другую структуру данных - отсортированное дерево, например, для сложности O (N) logN.

Answer 5

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