Problem: 1[0]1 Pattern Count

*Difficulty: Eazy

Given a string, your task is to find the number of patterns of form 1[0]1 where [0] represents any number of zeroes (minimum requirement is one 0) there should not be any other character except 0 in the [0] sequence.

 

Input:
The first line contains T denoting the number of testcases. Then follows description of testcases. Each case contains a string.
Output:
For each test case, output the number of patterns.

 

Constraints:
1<=T<=20
1<=Length of String<=2000
Example:
Input:
2
100001abc101
1001ab010abc01001

 

Output:
2
2

Implementation: Python2.7

def pattern_count(string):
    flag_index = string.find('1') # get the first '1' in string
    count = 0 # count number of patterns
    zero_between = 0 # count number of zero between two 1
    i = flag_index # start at first '1' in string
    while i < len(string) and i != -1:
        if string[i] == '0':
            zero_between += 1
        elif string[i] == '1':
            if zero_between > 0:
                count += 1
                zero_between = 0
            flag_index = i
        else:
            zero_between = 0
            flag_index = string.find('1', flag_index+1)
            i = flag_index
        i += 0 if i == -1 else 1
    print count

if __name__ == '__main__':
    t = input()
    for _ in range(t):
        string = raw_input().strip()
        pattern_count(string)
        

Advertisements