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

Question

Я работаю над программой Java, которая выполняет поиск через словарь для слов, составленных из определенного набора букв. Мне интересно, можно ли настроить регулярное выражение, которое позволит вам использовать символ только так часто, как оно появляется в строке. Например, с буквами SHARE. Слушайте, зайцы, море, и т. Д. Будут действительны. Но см. Или sarah не будет действительным, потому что у вас есть только один e или один a соответственно.

Answer 1

Вот один подход:

1. Итерация через массив строк, чтобы создать MultiMap<String, String> (если вы используете библиотеку Guava или HashMap<String, List<String>>, если вы используете java.util) где ключ отсортированный слово, а значения - это легальные слова для этой отсортированной строки. Это будет ваш шаг предварительной обработки, поэтому вам нужно будет сделать это только один раз. Последующие поиски будут относительно быстрыми, так как ваш хэш-файл уже существует (по сравнению с циклическим использованием вашего словаря каждый раз, чтобы соответствовать некоторому регулярному выражению, что было бы намного медленнее, чем использование хэш-карты).
2. Отсортируйте строку поиска и найдите все подстроки этой отсортированной строки.
3. Перейдите через отсортированное подмножество и найдите HashMap или MultiMap, чтобы получить значения для этой строки sortedsubset. Сохраните дорожку всех значений, и у вас есть ответ.

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

Answer 2

Если нет букв, которые появляются дважды в слове, так как не в share, вы могли бы использовать

^(?!([share]).*\\1)[share]+$ 

Это будет соответствовать любому слову, составленному из некоторых или всех букв в share.

Отрицательный взгляд (?!), содержащий обратную ссылку \\1 на то, что было сопоставлено в скобках, предотвращает совпадение, если письмо появляется более одного раза.

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

Answer 3

Регулярные выражения касаются соответствия шаблону. Найти простой шаблон, вероятно, будет невозможно.

Если вы действительно очень хотите регулярное выражение, эти функции будут генерировать один:

public static String permutation(String str) { 
    return "^" + permutation("",str).replaceFirst("\\|", "(") + ")$"; 
} 

private static String permutation(String prefix, String str) { 
    String s = ""; 
    int n = str.length(); 
    if (n == 0) return "|"+prefix; 
    else { 
     for (int i = 0; i < n; i++) 
      s += permutation(prefix + str.charAt(i)+"?", 
          str.substring(0, i) + str.substring(i+1, n)); 
    } 
    return s; 
} 

Для «доля» будет возвращать:

^(s?h?a?r?e?|s?h?a?e?r?|s?h?r?a?e?|s?h?r?e?a?|s?h?e?a?r?|s?h?e?r?a?|s?a?h?r?e?|s?a?h?e?r?|s?a?r?h?e?|s?a?r?e?h?|s?a?e?h?r?|s?a?e?r?h?|s?r?h?a?e?|s?r?h?e?a?|s?r?a?h?e?|s?r?a?e?h?|s?r?e?h?a?|s?r?e?a?h?|s?e?h?a?r?|s?e?h?r?a?|s?e?a?h?r?|s?e?a?r?h?|s?e?r?h?a?|s?e?r?a?h?|h?s?a?r?e?|h?s?a?e?r?|h?s?r?a?e?|h?s?r?e?a?|h?s?e?a?r?|h?s?e?r?a?|h?a?s?r?e?|h?a?s?e?r?|h?a?r?s?e?|h?a?r?e?s?|h?a?e?s?r?|h?a?e?r?s?|h?r?s?a?e?|h?r?s?e?a?|h?r?a?s?e?|h?r?a?e?s?|h?r?e?s?a?|h?r?e?a?s?|h?e?s?a?r?|h?e?s?r?a?|h?e?a?s?r?|h?e?a?r?s?|h?e?r?s?a?|h?e?r?a?s?|a?s?h?r?e?|a?s?h?e?r?|a?s?r?h?e?|a?s?r?e?h?|a?s?e?h?r?|a?s?e?r?h?|a?h?s?r?e?|a?h?s?e?r?|a?h?r?s?e?|a?h?r?e?s?|a?h?e?s?r?|a?h?e?r?s?|a?r?s?h?e?|a?r?s?e?h?|a?r?h?s?e?|a?r?h?e?s?|a?r?e?s?h?|a?r?e?h?s?|a?e?s?h?r?|a?e?s?r?h?|a?e?h?s?r?|a?e?h?r?s?|a?e?r?s?h?|a?e?r?h?s?|r?s?h?a?e?|r?s?h?e?a?|r?s?a?h?e?|r?s?a?e?h?|r?s?e?h?a?|r?s?e?a?h?|r?h?s?a?e?|r?h?s?e?a?|r?h?a?s?e?|r?h?a?e?s?|r?h?e?s?a?|r?h?e?a?s?|r?a?s?h?e?|r?a?s?e?h?|r?a?h?s?e?|r?a?h?e?s?|r?a?e?s?h?|r?a?e?h?s?|r?e?s?h?a?|r?e?s?a?h?|r?e?h?s?a?|r?e?h?a?s?|r?e?a?s?h?|r?e?a?h?s?|e?s?h?a?r?|e?s?h?r?a?|e?s?a?h?r?|e?s?a?r?h?|e?s?r?h?a?|e?s?r?a?h?|e?h?s?a?r?|e?h?s?r?a?|e?h?a?s?r?|e?h?a?r?s?|e?h?r?s?a?|e?h?r?a?s?|e?a?s?h?r?|e?a?s?r?h?|e?a?h?s?r?|e?a?h?r?s?|e?a?r?s?h?|e?a?r?h?s?|e?r?s?h?a?|e?r?s?a?h?|e?r?h?s?a?|e?r?h?a?s?|e?r?a?s?h?|e?r?a?h?s?)$ 

Очевидно, что это может быть упрощенным + оптимизированного совсем немного, но по-прежнему не очень хорошая идея.

EDIT: Функции для короткого выхода:

public static String permutation(String str) { 
    return "^(" + permutation("",str) + ")$"; 
} 

private static String permutation(String prefix, String str) { 
    String s = ""; 
    int n = str.length(); 
    if (n == 0) return prefix; 
    else { 
    for (int i = 0; i < n; i++) 
     if (i != n-1) 
     s += prefix + str.charAt(i) + "?(" + 
      permutation("", str.substring(0, i) + str.substring(i+1, n))+")|"; 
     else 
     s += prefix + str.charAt(i) + "?" + 
      permutation("", str.substring(0, i) + str.substring(i+1, n)); 
    } 
    return s; 
} 

Печать:

^(s?(h?(a?(r?(e?)|e?r?)|r?(a?(e?)|e?a?)|e?a?(r?)|r?a?)|a?(h?(r?(e?)|e?r?)|r?(h?(e?)|e?h?)|e?h?(r?)|r?h?)|r?(h?(a?(e?)|e?a?)|a?(h?(e?)|e?h?)|e?h?(a?)|a?h?)|e?h?(a?(r?)|r?a?)|a?(h?(r?)|r?h?)|r?h?(a?)|a?h?)|h?(s?(a?(r?(e?)|e?r?)|r?(a?(e?)|e?a?)|e?a?(r?)|r?a?)|a?(s?(r?(e?)|e?r?)|r?(s?(e?)|e?s?)|e?s?(r?)|r?s?)|r?(s?(a?(e?)|e?a?)|a?(s?(e?)|e?s?)|e?s?(a?)|a?s?)|e?s?(a?(r?)|r?a?)|a?(s?(r?)|r?s?)|r?s?(a?)|a?s?)|a?(s?(h?(r?(e?)|e?r?)|r?(h?(e?)|e?h?)|e?h?(r?)|r?h?)|h?(s?(r?(e?)|e?r?)|r?(s?(e?)|e?s?)|e?s?(r?)|r?s?)|r?(s?(h?(e?)|e?h?)|h?(s?(e?)|e?s?)|e?s?(h?)|h?s?)|e?s?(h?(r?)|r?h?)|h?(s?(r?)|r?s?)|r?s?(h?)|h?s?)|r?(s?(h?(a?(e?)|e?a?)|a?(h?(e?)|e?h?)|e?h?(a?)|a?h?)|h?(s?(a?(e?)|e?a?)|a?(s?(e?)|e?s?)|e?s?(a?)|a?s?)|a?(s?(h?(e?)|e?h?)|h?(s?(e?)|e?s?)|e?s?(h?)|h?s?)|e?s?(h?(a?)|a?h?)|h?(s?(a?)|a?s?)|a?s?(h?)|h?s?)|e?s?(h?(a?(r?)|r?a?)|a?(h?(r?)|r?h?)|r?h?(a?)|a?h?)|h?(s?(a?(r?)|r?a?)|a?(s?(r?)|r?s?)|r?s?(a?)|a?s?)|a?(s?(h?(r?)|r?h?)|h?(s?(r?)|r?s?)|r?s?(h?)|h?s?)|r?s?(h?(a?)|a?h?)|h?(s?(a?)|a?s?)|a?s?(h?)|h?s?)$ 

Answer 4

Ok вот пример того, как вы могли бы сделать это. Однако вы должны прочитать эти статьи о катастрофическом обратно отслеживании:

Runaway Regular Expressions: Catastrophic Backtracking

Regex Performance

^(?!.*s.*s)(?!.*h.*h)(?!.*a.*a)(?!.*r.*r)(?!.*e.*e)(?![^share]).*$ 

Если вы хотите разрешить 2 буквы «s», как акции, чтобы слово створку вы могли бы сделать это как ,

^(?!.*s.*s.*s)(?!.*h.*h)(?!.*a.*a)(?!.*r.*r)(?!.*e.*e)(?![^share]).*$ 

идея быть менее 3-х «ы» в слово в порядке ...

Answer 5

Подход, который не использует сопоставление с образцом, но попадает в корень проблемы, является создание массив со счетом каждого символа в целевом слове: «глухой» будет массив (1,0,0,1,1,1,0,0, ...).

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