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

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

Input 8888338385
     Output VALID
Input 887837348234 
Output : Invalid

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

Ответ 1

РЕДАКТИРОВАТЬ: Благодаря Люку Торайлу для значительного улучшения исходного алгоритма.

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

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

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

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

Стоит отметить, что в отношении Niklas Baumstark отличное сравнение производительности что наши два решения на самом деле одинаковы. Булевский массив, построенный здесь, идентичен таблице перехода, которую вы построили в двухзначном DFA, принимающем [c ₁ с <суб > 2суб > ...] *. Я предполагаю, что единственное отличие заключается в том, что реализация Java, будучи намного более общей, несет намного больше накладных расходов.

Ответ 2

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: В отличие от моих предположений, Java, похоже, suck при оптимизации используемого здесь регулярного выражения, что приводит к неэффективный код. Даже регулярные выражения 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();
  }
}

Ответ 3

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

Ответ 4

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

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

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

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

EDIT: Я понимаю, что это обман, но в вопросе, который исключает это, нет ничего.

Ответ 5

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