Gegeben eine Zeichenfolge, die nur aus 0, 1 oder 2s besteht, zählen Sie die Anzahl der Teilstrings, die die gleiche Anzahl von 0s, 1s und 2s haben

Question

Ich versuche, Algorithmus/Datenstruktur zu lernen. Um mein Wissen zu verbessern, versuche ich einige der Online-Probleme zu lösen. Eines der Probleme zu lösen, ich versuche

bei practiceque gegeben

Ich habe versucht, unter Methode:

def count_zero_one_two(): 
    s = '102100211' 
    s_len = len(s) 
    count = 0 
    for i in range (s_len-1): 
     j = i+1 
     k = j+1 
     #print i, j, k, count 
     #print s[i], s[j], s[k] 
     if k > (s_len-1): 
      print "end" 
      break 

     elif (s[i] != s[j]) and (s[i] !=s[k]) and (s[j] != s[k]): 
      print s[i], s[j], s[k] 
      print "not equal" 
      count = count+1 
      #print count 
     else: 
      print s[i], s[j], s[k] 
      print "equal" 
     k = j +i 
    print count 


count_zero_one_two() 

Frage: wenn meine Eingabezeichenfolge ist „102100211“, dann sollte 5 zählen, aber ich bin bekommen 4. Irgendeine Idee?

Answer 1

Ich würde es so lösen:

def count_zero_one_two(s): 
    num = 0 
    for i in range(len(s)): 
     for j in range(1, len(s)/3 + 1): 
      if all(s[i:i+3*j].count(n) == j for n in '012'): 
       num += 1 
    return num 

all() verwendet wird, um zu überprüfen, dass alle drei Zeichen (für jede Wiederholung) sind in ‚012‘.

Die innere for Schleife wird verwendet, um die Zahl von 0, 1 und 2 in Folgen der Länge 3, 6, 9 usw.

Output zu zählen:

>>> s = '0102010' 
>>> count_zero_one_two(s) 
2 
>>> 
>>> s = '102100211' 
>>> count_zero_one_two(s) 
5 

Answer 2

from collections import Counter 

def countSub(s): 
    result = [] 

    for i in range(3, len(s), 3): 
     t = s[:i] 
     c = list(Counter(t).values()) 
     if (c[0]==c[1]==c[2]): 
      result.append((t, c[0])) 

    return result 


def count(s): 
    result = [] 
    for i in range(len(s)-2): 
     result.extend(countSub(s[i:])) 

    return set(result) 




ss = count("102100211")  
print("%s substrings found: " % len(ss), ss)  

Ausgabe:

4 substrings found (not counting duplicates and empty strings): 
    {('021', 1), ('210021', 2), ('210', 1), ('102', 1)}