2132 - Min Subsir: Diferență între versiuni

De la Universitas MediaWiki
mFără descriere a modificării
Fără descriere a modificării
 
Linia 8: Linia 8:
== Restricții și precizări ==
== Restricții și precizări ==
* 1 ⩽ lungime sir ⩽ 10000
* 1 ⩽ lungime sir ⩽ 10000
== Exemplu ==
== Exemplul 1 ==
; Intrare
; Intrare
: aadcaabcbacadca
: aadcaabcbacadca
; Ieșire
; Ieșire
: Datele introduse corespund restricțiilor impuse.
: 5
: 5
<br>
== Exemplul 2 ==
; Intrare
: 54454534
; Ieșire
: Datele introduse nu corespund restricțiilor impuse.
<br>
== Explicație ==
== Explicație ==
Sunt folosite literele: '''a,b,c,d'''.
Sunt folosite literele: '''a,b,c,d'''.
Linia 19: Linia 27:
== Rezolvare ==
== Rezolvare ==
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line>
def lungime_minima(s):
# 2132 -Min Subsir
     # Creăm un set pentru a stoca toate literele unice din șir
def verificare(verif_car):
     litere_unice = set(s)
     # Verificăm dacă lungimea șirului este în intervalul [1, 10000]
     # Inițializăm lungimea minimă cu lungimea șirului
     if 1 <= len(verif_car) <= 10000:
     lungime_min = len(s)
        # Verificăm dacă șirul conține doar litere mici ale alfabetului englez
    # Parcurgem șirul cu o fereastră de caractere
        if not all(c.islower() for c in verif_car if not c.isspace()):
     for i in range(len(s)):
            # Dacă șirul conține alte caractere, ridicăm o excepție
         for j in range(i, len(s)):
            raise ValueError
            # Dacă fereastra conține toate literele unice, actualizăm lungimea minimă
        # Dacă șirul este valid, îl returnăm
             if set(s[i:j+1]) == litere_unice:
        return verif_car
     else:
        # Dacă șirul nu este valid, ridicăm o excepție
        raise ValueError
 
 
# Funcția lungime_minima determină lungimea minim
def lungime_minima(min_lung):
    litere_unice = set(min_lung)
     lungime_min = len(min_lung)
     for i in range(len(min_lung)):
         for j in range(i, len(min_lung)):
             if set(min_lung[i:j+1]) == litere_unice:
                 lungime_min = min(lungime_min, j-i+1)
                 lungime_min = min(lungime_min, j-i+1)
   
    # Returnăm lungimea minimă
     return lungime_min
     return lungime_min


s = input()
 
print(lungime_minima(s))
if __name__ == "__main__":
    try:
        # Citim șirul de la utilizator
        s = input("Introduceti sirul de caractere: ")
        # Validăm șirul
        s = verificare(s)
        print("Datele introduse corespund restricțiilor impuse.")
        print(lungime_minima(s))
    except ValueError:
        # Dacă șirul nu este valid, afișăm un mesaj de eroare
        print("Datele introduse nu corespund restricțiilor impuse.")


</syntaxhighlight>
</syntaxhighlight>

Versiunea curentă din 12 noiembrie 2023 15:16

Se consideră un șir de caractere format din litere mici ale alfabetului englez.

Cerinţa

Să se determine lungimea minimă a unei secvențe care conține toate literele întâlnite în șirul inițial.

Date de intrare

Programul citește de la tastatură șirul de caractere.

Date de ieşire

Programul va afișa pe ecran lungimea secvențele cerute.

Restricții și precizări

  • 1 ⩽ lungime sir ⩽ 10000

Exemplul 1

Intrare
aadcaabcbacadca
Ieșire
Datele introduse corespund restricțiilor impuse.
5


Exemplul 2

Intrare
54454534
Ieșire
Datele introduse nu corespund restricțiilor impuse.


Explicație

Sunt folosite literele: a,b,c,d.

Secvențe de lungime minimă care folosesc toate literele: dcaab, bacad.

Rezolvare

# 2132 -Min Subsir
def verificare(verif_car):
    # Verificăm dacă lungimea șirului este în intervalul [1, 10000]
    if 1 <= len(verif_car) <= 10000:
        # Verificăm dacă șirul conține doar litere mici ale alfabetului englez
        if not all(c.islower() for c in verif_car if not c.isspace()):
            # Dacă șirul conține alte caractere, ridicăm o excepție
            raise ValueError
        # Dacă șirul este valid, îl returnăm
        return verif_car
    else:
        # Dacă șirul nu este valid, ridicăm o excepție
        raise ValueError


# Funcția lungime_minima determină lungimea minim
def lungime_minima(min_lung):
    litere_unice = set(min_lung)
    lungime_min = len(min_lung)
    for i in range(len(min_lung)):
        for j in range(i, len(min_lung)):
            if set(min_lung[i:j+1]) == litere_unice:
                lungime_min = min(lungime_min, j-i+1)
    return lungime_min


if __name__ == "__main__":
    try:
        # Citim șirul de la utilizator
        s = input("Introduceti sirul de caractere: ")
        # Validăm șirul
        s = verificare(s)
        print("Datele introduse corespund restricțiilor impuse.")
        print(lungime_minima(s))
    except ValueError:
        # Dacă șirul nu este valid, afișăm un mesaj de eroare
        print("Datele introduse nu corespund restricțiilor impuse.")