Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can I count the number of occurrences of a simple pattern in a string?

Tags:

java

string

For this question, a "pair" in a string is defined as a situation where two instances of one character are separated by another character. So in "AxA" the A's make a pair. Pairs can overlap, so "AxAxA" contains three pairs; two for A and one for x.

Further examples:

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

I was asked how to compute the number of pairs in a given string in an interview yesterday, and I'm not sure how to do it.

like image 462
Deepak Avatar asked Mar 22 '11 15:03

Deepak


2 Answers

An O(n) solution would be to iterate the string (from 0 to length-2) and (using charAt(..)) to verify whether the current character is equal to the current+2. If so, increment a pairsCount variable

int pairsCount = 0;
for (int i = 0; i < str.length() - 2; i ++) {
   if (str.charAt(i) == str.charAt(i + 2)) {
      pairsCount ++;
   }
}
like image 135
Bozho Avatar answered Oct 22 '22 01:10

Bozho


The previous awser don't covert the fact that the caracter in the middle (the separator) must be different.

For this question, a "pair" in a string is defined as a situation where two instances of one character are separated by another character. So in "AxA" the A's make a pair. Pairs can overlap, so "AxAxA" contains three pairs; two for A and one for x.

Must this characters be different ? Here what I though if it's have to be different...

    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++;
        }
    }
like image 37
Chris Avatar answered Oct 22 '22 00:10

Chris