Символ из списка в строке

Question

Доброе утро,

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

Скажем, у меня есть список L символов и строка S. Я хочу знать, принадлежит ли каждый символ в S к L, и единственное решение, о котором я не могу думать в данный момент, - тривиальное

boolean Result = true
boolean Temp = false

for i from 1 to S.Length
    Temp <- false
    for j from 1 to A.Count
        if (S[i] == A[j]) Temp <- true

    Result = Result && Temp

return Result

Пожалуйста, обратите внимание, что я не забочусь об оптимизации этого алгоритма, что можно легко сделать, но вместо этого для лучшего алгоритма. Может кто-нибудь, пожалуйста, помогите мне разобраться? Также обратите внимание, что большую часть времени S.Length намного больше, чем A.Count. Наконец, я не хочу использовать регулярные выражения.

Большое спасибо.

Answer 1

Здесь перебор списка символов стоит O (A.Count). Вы можете хранить символы в хеш-таблице , таким образом, вы можете определить, принадлежит ли S [i] A в постоянное время, при условии правильного выбора хеш-функции.

Таким образом, с хорошей хеш-функцией вы бы снизили глобальные затраты с O (S.Length * A.Count) до O (S.Length).

Если вы имеете дело с символами ASCII, то ваша хеш-таблица может быть тривиально уменьшена до массива из 128 элементов с идентификатором как «хеш-функция». Если вы имеете дело с символами Unicode, но ваши тексты содержат большинство символов ASCII, то вы можете подумать об этом варианте.

Answer 2

Не могли бы вы просто посчитать символы в S и L, а затем сравнить их?Это позволяет избежать структуры вложенных циклов, поэтому я думаю, что это O (N + M), а не O (MN) (где M и N - длины строки).

int[] Lcount = new int[256];
int[] Scount = new int[256];

for (int i=0;i<L.length;++i) {
  Lcount[L.charAt(i)]++;
}

for (int i=0;i<S.length;++i) {
  Scount[S.charAt(i)]++;
}

for (int i=0;i<256;i++) {
   // S doesn't have the characters in L so can't be a subset
   if (Scount[i] < Lcount[i]) {
      return false;
   }
}

return true;

В приведенном выше примере предполагается ASCIIпредставление символов, вы можете применить такую ​​же идею, используя хэш-таблицу, если количество символов было больше, чем ASCII (например, Unicode).

Answer 3

Вы можете сортировать по алфавиту L и S, например, используя быструю сортировку.Теперь вы можете сравнивать символ за символом L и S, поэтому ваше время будет O(n1 log n1) (for sort of L) + O(n2 log n2) (for sort of S) + Max(n1, n2) (for comparing the two sorted strings character by character), где n1 = L.Length и n2 = S.Length Итак, учитывая n = Max(n1, n2), у вас должно быть время O(n log n) (надеюсь)-)

Точная реализация зависит от того, как вы хотите обрабатывать несколько одинаковых букв.Если L = "A" и S = "AA", соответствует ли S 1015 *?