Java String Matching the Regex

Question

I am trying to solve the following problem.

Given a string and a Regular Expression pattern, give the number of the times the pattern occurs in the string. RegEx symbols mean as follows:

. - 2 occurrences of the previous character, 
+ - 4 occurrences of previous character, 
* – more than 5 occurrences of the previous character

Sample Input given:

aaaaaannndnnnnnnfffhfhhgjjjwkkkllclc
a.
n+
a*
an.
a.d.

Sample Output given:

My approach is to convert all the RegEx to normal pattern. i.e., for the above example my RegEx would be:

aa
nnnn
aaaaaa
ann
aadd

and then count the occurrences. But I am clueless what to do if the input RegEx is:

a*d.

Please note that I cannot use any inbuilt functions like Pattern.Matches. Any suggestions?

Thank you.

* is unbound (any number larger than 5), so you can't actually make the pattern explicit, since a* is an infinite set of finite strings. Besides, whoever arbitrarily redefined + and * should be aware she is likely to cause much confusion. — Stefano Sanfilippo
– Stefano Sanfilippo, Commented Dec 13, 2014 at 10:56
If you cannot use builtin functions, what good is converting the patterns to "real" regex patterns? Can you use regex for this task or not? — Aran-Fey
– Aran-Fey, Commented Dec 13, 2014 at 11:54
How would you implement your regex matching if this rule is given is the question? @Rawing This is an interview question. You can check it here. geeksforgeeks.org/browserstack-written-test-3 I tried to solve this problem by expanding the regex. Just an approach. — user2761431
– user2761431, Commented Dec 13, 2014 at 12:50

Aleksei Shestakov · Accepted Answer · 2014-12-13 12:45:55Z

1

Here is an example of method that would parse your pattern and tell you if the input string starts with specified pattern. I didn't finish it, because i think it is some kind of home work:

boolean startsWithPattern(String pattern, String str) {
    int strPos = 0;
    int patternPos = 0;
    // parse pattern and check input str
    while (patternPos < pattern.length()) {
        char symbol = pattern.charAt(patternPos);
        // TODO this will not work for patterns like `a`, only for `a.`, `b*`, `n+`
        char action = pattern.charAt(patternPos + 1); 
        patternPos += 2;
        switch (action) {
            case '.':
                int end = strPos + 2; // check only two symbols
                for (; strPos < end; ++strPos) {
                    if (str.charAt(strPos) != symbol) {
                        return false; // string don't match
                    }
                }                    
                break;
            case '*':
                // TODO some cycle that would check 5+ positions in str
                break;
            case '+':
                // TODO similar to '.'
                break;
        }
    }
    return true; // string starts with pattern!
}

answered Dec 13, 2014 at 12:45

Aleksei Shestakov

2,5482 gold badges15 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user2761431 Over a year ago

This is not a homework problem. You can find my implementation at ideone.com/06CQSO And I believe you haven't addressed my problem. I am stuck at how to solve the problem for the input : a*d.

Aleksei Shestakov Over a year ago

You can solve the problem for pattern a*d. with your current approach, but the solution would be very uneffective. It seems very painfull to generate all 'normal patterns' for pattern a*d. and than search them in string of length 100000 (as example).

Collectives™ on Stack Overflow

Java String Matching the Regex

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related