Find all the patterns of “1(0+)1” in a given string using Python Regex

A string contains patterns of the form 1(0+)1 where (0+) represents any non-empty consecutive sequence of 0’s. Count all such patterns. The patterns are allowed to overlap. Note : It contains digits and lowercase characters only. The string is not necessarily a binary. 100201 is not a valid pattern. Examples:

Input : 1101001
Output : 2

Input : 100001abc101
Output : 2

We have existing solution for this problem please refer Find all the patterns of “1(0+)1” in a given string link. Another set containing similar solution using regex in java is also published. We will solve this problem quickly in python using Regex. Approach is very simple :

1. Search a first sub-string in original string which follows ’10+1′ pattern using re.search(regex,string) method.
2. substr = re.search(regex,string) return None if it doesn’t find given regex as sub-string in original string otherwise it returns first matched sub-string which follows ’10+1′ pattern. substr.start() gives us starting index of matched regex and substr.end() gives us ending index of matched regex.
3. Whenever we find regex as sub-string then increase count by 1 and again search for given regex starting from ending index of previous sub-string.

Output:

2

Time Complexity : O(N)

Space Complexity : O(1)