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

Answer 4

Еще одно решение, на которое стоит взглянуть...

public String wordEnds(String str, String word) {
  if(str.equals(word)) return "";
  int i = 0;
  String result = "";
  int stringLen = str.length();
  int wordLen = word.length();
  int diffLen = stringLen - wordLen;
  
  while(i<=diffLen){
    if(i==0 && str.substring(i,i+wordLen).equals(word)){
      result = result + str.charAt(i+wordLen);
    }else if(i==diffLen && str.substring(i,i+wordLen).equals(word)){
      result = result + str.charAt(i-1);
    }else if(str.substring(i,i+wordLen).equals(word)){
      result = result + str.charAt(i-1) + str.charAt(i+wordLen) ;
    }
    
    i++;
  }
  
  if(result.length()==1) result = result + result;
  
  return result;
}

Answer 5

Другое возможное решение:

      public String wordEnds(String str, String word) {
  String result = "";
  
  if (str.contains(word)) {
    for (int i = 0; i < str.length(); i++) {
      if (str.startsWith(word, i)) {
        if (i > 0) {
        result += str.charAt(i - 1);
        }
        if ((i + word.length()) < str.length()) {
        result += str.charAt(i + word.length());
        }
      }
    }
  }
  
  return result;
}