Как подсчитать количество вхождений простого шаблона в строку?

Question

Для этого вопроса «пара» в строке определяется как ситуация, когда два экземпляра одного символа разделены другим символом. Так что в «AxA» А составляют пару. Пары могут перекрываться, поэтому «AxAxA» содержит три пары; два для А и один для х.

Дополнительные примеры:

countPairs ("axa") → 1
countPairs ("axax") → 2
countPairs ("axbx") → 1

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

Answer 1

Решение O (n) состоит в том, чтобы выполнить итерацию строки (от 0 до length-2) и (используя charAt(..)) проверить, равен ли текущий символ current+2.Если это так, увеличьте переменную pairsCount

int pairsCount = 0;
for (int i = 0; i < str.length() - 2; i ++) {
   if (str.charAt(i) == str.charAt(i + 2)) {
      pairsCount ++;
   }
}

Answer 2

Предыдущий awser не скрывает тот факт, что символ в середине (разделитель) должен быть другим.

Для этого вопроса «пара» в строке определяется как ситуация, когда два экземпляра одного символа разделены другим символом . Так что в «AxA» А составляют пару. Пары могут перекрываться, поэтому «AxAxA» содержит три пары; два для А и один для х.

Должны ли эти персонажи отличаться? Вот что я думаю, если это должно быть иначе ...

    int trueNbPair =0;
    for (int i=1;i<str.length()-1;i++)
    {
        char prev = str.charAt(i-1);
        char current = str.charAt(i);
        char next = str.charAt(i+1);

        if (prev == next && current!= prev)
        {
            trueNbPair++;
        }
    }