7
\$\begingroup\$

A string contains many patterns of the form 1(0+)1 where (0+) represents any non-empty consecutive sequence of 0's. The patterns are allowed to overlap.

For example, consider string "1101001", we can see there are two consecutive sequences "1(0)1" and "1(00)1" which are of the form 1(0+)1.

enter image description here

public class Solution {

        static int patternCount(String s){
            String[] sArray = s.split("1");
            for(String str : sArray) {
                if(Pattern.matches("[0]+", str)) {
                    count++;
                }
            }
            return count;
        }

        public static void main(String[] args) {
            int result = patternCount("1001010001");
            System.out.println(result);//3
        }
    }

Sample Input:

100001abc101, 1001ab010abc01001, 1001010001

Sample Output:

2 2 3

But still something i feel might fail in future could you please help me to optimize my code as per the Requirement

\$\endgroup\$
1
  • \$\begingroup\$ You should explicitly state what the instruction for this challenge is. \$\endgroup\$
    – Legato
    Jun 13, 2017 at 13:55

4 Answers 4

4
\$\begingroup\$

You can accomplish this by using positive look-behind in your regex and simply counting the number of matches.

static int patternCount(String s) {
   Pattern pattern = Pattern.compile("(?<=1)[0]+(?=1)");
   Matcher  matcher = pattern.matcher(s);
   int count = 0;
   while (matcher.find()) {
        count++;
   }
   return count;
}
\$\endgroup\$
2
  • 2
    \$\begingroup\$ An explanation is missing here, what does your code change, why is it better than the original code? \$\endgroup\$
    – Daniel
    Jun 13, 2017 at 14:33
  • 1
    \$\begingroup\$ Agreed with @coal_. I don't really get why the positive look behind is required here. \$\endgroup\$
    – Imus
    Jun 13, 2017 at 14:47
5
\$\begingroup\$

Although the other 2 answers currently given are technically correct. I find it more logical to search for a 1 followed by any number of 0's ending with another 1 which we cannot consume yet (as it can be used again in the following match).

So the pattern should look like 1[0]+(?=1)

Which turns the method implementation to this:

static int patternCount(String s) {
    Pattern pattern = Pattern.compile("1[0]+(?=1)");
    Matcher matcher = pattern.matcher(s);
    int count = 0;
    while (matcher.find()) {
        count++;
    }
    return count;
}
\$\endgroup\$
0
1
\$\begingroup\$

If all you want to do is count the pattern's occurences, use matcher.find We also need a positive look behind for when the start includes the last match's end.

import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class PatternCount {
    public static void main(String[] args) {
        Pattern pattern = Pattern.compile("(?<=1)0+1");
        String[] cases = {"100001abc101", "1001ab010abc01001", "1001010001"};
        for (String testCase : cases) {
            System.out.printf("Count in %s: %d%n", testCase, countPattern(testCase, pattern));
        }
    }


    private static int countPattern(String testCase, Pattern pattern) {
        int count = 0;
        Matcher matcher = pattern.matcher(testCase);
        while (matcher.find()) {
            count++;
        }
        return count;
    }
}

Output:
enter image description here

\$\endgroup\$
3
  • \$\begingroup\$ Any reason why the positive look behind instead of a non consuming look ahead? \$\endgroup\$
    – Imus
    Jun 13, 2017 at 14:48
  • 2
    \$\begingroup\$ They're equivalent in this case, the look ahead is probably better performance wise though now that you mention it. \$\endgroup\$
    – Legato
    Jun 13, 2017 at 14:52
  • \$\begingroup\$ its look cool will see this also \$\endgroup\$ Jun 13, 2017 at 16:05
1
\$\begingroup\$

you should just count the pattern from the first character to the end.So using regex it would be easier to find ..

static int patternCount(String s)   {
     String regex = "1(0+)1";
     Pattern pattern = Pattern.compile(regex);
     Matcher matcher = pattern.matcher(s);
     int from = 0;
     int count = 0;
     while(matcher.find(from)) {
        count++;    
        from = matcher.start() + 1;
     }
    return count;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.