Codingbat wordEnds с использованием regex

Я пытаюсь решить wordEnds from codingbat.com с помощью regex.

Учитывая строку и непустую строку слова, верните строку, состоящую из каждого char, непосредственно перед и сразу после каждого появления слова в строке. Игнорировать случаи, когда char нет или после слова, а char может быть дважды включен, если он находится между двумя словами.

wordEnds("abcXY123XYijk", "XY") → "c13i"
wordEnds("XY123XY", "XY") → "13"
wordEnds("XY1XY", "XY") → "11"
wordEnds("XYXY", "XY") → "XY"

Это самое простое, поскольку я могу сделать это с моим текущим знанием регулярного выражения:

public String wordEnds(String str, String word) {
  return str.replaceAll(
     ".*?(?=word)(?<=(.|^))word(?=(.|$))|.+"
       .replace("word", java.util.regex.Pattern.quote(word)),
     "$1$2"
  );
}

replace используется для размещения в фактической строке word в шаблоне для удобочитаемости. Pattern.quote не обязательно передавать свои тесты, но я думаю, что это необходимо для правильного решения на основе регулярных выражений.

Регулярное выражение имеет две основные части:

  • Если после сопоставления как можно большего количества символов ".*?", word все еще можно найти "(?=word)", затем найдите, чтобы захватить любой символ, предшествующий ему "(?<=(.|^))", совпадение "word", и посмотрите, чтобы захватить любой символ после него "(?=(.|$))".
    • Исходный тест "if" гарантирует, что атомный lookbehind захватывает, только если есть word
    • Использование lookahead для захвата следующего символа не потребляет его, поэтому его можно использовать как часть дальнейшего сопоставления
  • В противном случае сопоставьте то, что осталось "|.+"
    • Группы 1 и 2 будут записывать пустые строки

Я думаю, что это работает во всех случаях, но это, очевидно, довольно сложно. Мне просто интересно, могут ли другие предложить более простое регулярное выражение для этого.

Примечание. Я не ищу решение с помощью indexOf и цикла. Я хочу решение replaceAll на основе регулярного выражения. Я также нуждаюсь в рабочем регулярном выражении, которое передает все тесты кодирования.

Мне удалось уменьшить появление word внутри шаблона только до одного.

".+?(?<=(^|.)word)(?=(.?))|.+"

Я все еще смотрю, можно ли это упростить, но у меня также есть другой вопрос:

  • С помощью этого последнего шаблона я упростил .|$ только .?, но если я попытался упростить ^|. до .?, это не сработает. Почему это?

Ответы

Ответ 1

На основе вашего решения мне удалось немного упростить код:

public String wordEnds(String str, String word) {
  return str.replaceAll(".*?(?="+word+")(?<=(.|^))"+word+"(?=(.|$))|.+","$1$2");
}

Другой способ записи:

public String wordEnds(String str, String word) {
  return str.replaceAll(
     String.format(".*?(?="+word+")(?<=(.|^))"+word+"(?=(.|$))|.+",word),
     "$1$2");
}

Ответ 2

С помощью этого последнего шаблона я упростил .|$ только .?, но если я попытался упростить ^|. до .?, это не сработает. Почему это?

В реализации Oracle поведение look-behind выглядит следующим образом:

  • "Изучая" регулярное выражение (с методом study() в каждом node), он знает максимальную длину и минимальную длину шаблона в группе look-behind. (Метод study() - это то, что допускает очевидную длину внешнего вида)
  • Он проверяет внешний вид , начиная совпадение в каждой позиции от индекса (current - min_length) до позиции (current - max_length) и выходит раньше, если условие выполнено.

Эффективно, он попытается сначала проверить внешний вид в кратчайшей строке.

Реализация умножает сложность соответствия на коэффициент O (k).

Это объясняет, почему смена ^|. на .? не работает: из-за стартовой позиции она эффективно проверяет word до .word. Здесь нет квантификатора, так как упорядочение задается диапазоном соответствия.

Вы можете проверить код метода match в Pattern.Behind и Pattern.NotBehind внутренних классах, чтобы проверить, что я сказал выше.

В отличие от .NET, look-behind, скорее всего, реализуется функцией обратного сопоставления, а это означает, что никакой сложности не возникает при сопоставлении сложности.

Мое подозрение связано с тем, что группа захвата в (?<=(a+))b соответствует всем a в aaaaaaaaaaaaaab. Показано, что квантификатор имеет свободное владение в группе поиска.

Я тестировал, что ^|. можно упростить до .? в .NET, и регулярное выражение работает правильно.

Ответ 3

Я работаю в .NET regex, но мне удалось изменить ваш шаблон на:

.+?(?<=(\w?)word)(?=(\w?))|.+

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

Он может ответить, почему вам не нужно указывать якоря ^ и $, для чего именно $ - это \r или \n или другое? (У .NET есть проблемы с $, и, возможно, вы не совсем захватываете Null из $, но нулевое значение \r или \n, которое позволило вам перейти на .? для $)