J'ai essayé LeetCode tous les jours 20. Parenthèses valides (Python, Go)

introduction

@Ishishow gère un site de mots anglais gratuit E-tan.

J'aimerais travailler quotidiennement sur letcode pour améliorer mes capacités de programmeur et donner ma propre façon de le résoudre.

Qu'est-ce que Leetcode

leetcode.com C'est la pratique de coder des interviews pour les développeurs de logiciels. Au total, plus de 1 500 questions de codage ont été affichées, et il semble que les mêmes questions soient souvent posées lors d'entretiens réels.

Introduction au langage Go + Algorithme Je vais le résoudre avec Golang et Python pour renforcer mon cerveau. (Python est faible mais expérimenté)

6ème question (problème 20)

20. Valid Parentheses

• Contenu du problème (traduction japonaise)

Considérez qu'une chaîne s contient uniquement des caractères '(', ')', '{', '}', `` ['' et ']', entrée Déterminez si la chaîne est valide.

La chaîne d'entrée est valide dans les cas suivants:

1. Les supports ouverts doivent être fermés avec le même type de support.
2. Les crochets ouverts doivent être fermés dans le bon ordre.

Example 1:

  Input: s = "()"
  Output: true

Example 2:

  Input: s = "()[]{}"
  Output: true

Example 3:

  Input: s = "(]"
  Output: false

Example 4:

  Input: s = "([)]"
  Output: false

Example 5:

  Input: s = "{[]}"
  Output: true

Façon de penser

1. Préparez un tableau de pile et un dictionnaire (carte).
2. Entrez le symbole correspondant sur la carte
3. Regardez la chaîne caractère par caractère, ajoutez-la à la pile si elle commence par une parenthèse, et si c'est une parenthèse fermante, retirez la dernière de la pile et vérifiez si elle correspond.

Explication

1. Définissez pile et dict (carte).
2. dict = {"]":"[", "}":"{", ")":"("}
3. Regardez les caractères un par un avec l'instruction for.

--Code de réponse

class Solution:
	def isValid(self, s):
		stack = []
		dict = {"]":"[", "}":"{", ")":"("}
		for char in s:
			if char in dict.values():
				stack.append(char)
			elif char in dict.keys():
				if stack == [] or dict[char] != stack.pop():
					return False
			else:
				return False
		return stack == []

If char in dict.values (): s'il commence par des parenthèses

Elif char in dict.keys (): s'il se termine entre parenthèses

Obtenez les derniers personnages de la pile avec pop

Attribuer à empiler avec append.

• Je l'écrirai aussi en Go!

  func isValid(s string) bool {
  	stack := make([]rune, 0)
  	m := map[rune]rune{
  		')': '(',
  		']': '[',
  		'}': '{',
  	}
  	for _, c := range s {
  		switch c {
  		case '(', '{', '[':
  			stack = append(stack, c)
  		case ')', '}', ']':
  			if len(stack) == 0 || stack[len(stack)-1] != m[c] {
  				return false
  			}
  			stack = stack[:len(stack)-1]
  		}
  	}
  
  	return len(stack) == 0
  }

Ce code est un peu délicat, mais j'ai ce code pour voir les chaînes caractère par caractère dans Go.

Pour _, c: = range, le traitement en boucle lit les chaînes de caractères caractère par caractère. À ce moment-là, c devient le type de rune, donc la carte et la pile sont également définies avec le type de rune.

Depuis que j'écris Golang, j'ai écrit le processus avec la déclaration switich.

-Self memo (Go)

Si vous regardez la chaîne de caractères caractère par caractère, rune

Ajouter à la tranche (ok car ce n'est pas une longueur fixe)