如何计算字符串中简单模式的出现次数？

Question

对于这个问题,字符串中的"对"被定义为一个字符的两个实例被另一个字符分隔的情况.因此,在"AxA"中,A成为一对.对可以重叠,因此"AxAxA"包含三对; 两个用于A,一个用于x.

更多例子:

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 ++;
   }
}