Hackerrank Woche der Code 33 Pattern Count

Question

Hallo Ich habe diese Frage auf Hackerrank versucht. Ich habe versucht, Regex in Python. Aber es schlägt im Testfall "1001010001" fehl. Kann mir bitte jemand helfen? Es gibt Ausgabe als 2, aber erwartete Ausgabe ist 3. (wie in 1001 101 10001). Wie funktioniert Python eigentlich gut behandeln (im Sinne eines Algorithmus?)

https://www.hackerrank.com/contests/w33/challenges/pattern-count

import re 
text=(raw_input().strip('\n')) 
patregex=re.compile(r'1(0)*1') 
p=patregex.findall(text) 
print(len(p)) 

Answer 1

Ein regulärer Ausdruck ist nicht überlappende Matches zählen.

Sie können jedoch den Code leicht modifizieren, zu:

import re 

patregex=re.compile(r'10*1') 

text= raw_input().strip('\n') 

cnt = 0 
pos = 0 
match = patregex.search(text) 
while match: 
    match = patregex(text,match.end()-1) 
    cnt += 1 
print(cnt)

hier also, wenn wir einen match finden, werden wir versuchen, ein anderes Spiel Anfahr- und match.end()-1 des vorherigen Spiel zu finden, bis kein anderes Spiel kann gefunden werden. Wir tun dies, bis keine Übereinstimmung mehr gefunden werden kann. Für jedes Spiel erhöhen wir die cnt += 1.

Wir können match.end()-1 verwenden, da jedes Spiel mit einem von null oder mehr 0s gefolgt 1 beginnt und eine andere 1. So wissen wir, dass das Muster kann nur Neustart im letzten Spiel.

Der Ansatz wird auch auf Speicher sparen: da, nachdem Sie ein erstes Spiel finden Sie einfach über dieses Spiel vergessen können, wenn für die nächsten suchen. Ein findall(..) Ansatz, muss alle Übereinstimmungen im Speicher zur gleichen Zeit speichern.

Answer 2

Es kann durch einen regulären Ausdruck und einem Blick in die Zukunft Muster zu fangen den Fall einer Überlappung 1 gelöst werden:

import re 

def count_code33(input_string): 
    return len(re.findall('10*(?=1)', input_string)) 

# Test section  
def test(input_string): 
    print('{!r} => {}'.format(input_string, count_code33(input_string))) 

test('') 
test('0') 
test('10') 
test('1001010001') 
test('1001 101 10001') 
test('100110110001') 
test('1111') 

Ergebnis:

'' => 0 
'0' => 0 
'10' => 0 
'1001010001' => 3 
'1001 101 10001' => 3 
'100110110001' => 5 
'1111' => 3