codingbat wordEnds, используя регулярные выражения

Question

Я пытаюсь решить wordEnds с сайта codingbat.com с помощью регулярных выражений.

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

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 msgstr "и смотреть вперед, чтобы захватить любой символ, следующий за ним" (?=(.|$)) ".
  • Первоначальный тест "если" гарантирует, что атомный взгляд захватывает только при наличии word
  • Использование Lookahead для захвата следующего символа не потребляет его, поэтому его можно использовать как часть дальнейшего соответствия
• В противном случае совпадать с тем, что осталось "|.+"
  • Группы 1 и 2 будут захватывать пустые строки

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

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

---

Мне удалось уменьшить вхождение word в шаблоне до одного.

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

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

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

Answer 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");
}

Answer 2

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

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

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

По сути, он сначала попытается проверить поиск самой короткой строки.

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

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

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

---

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

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

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

Answer 3

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

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

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

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