J'ai essayé LeetCode tous les jours 14.Le plus long préfixe commun (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é)

5e question (problème 14)

14.Longest Common Prefix

• Contenu du problème (traduction japonaise)

Ecrivez une fonction qui trouve la plus longue chaîne de préfixe commune dans un tableau de chaînes.

S'il n'y a pas de préfixe commun, il renvoie une chaîne vide " ".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Façon de penser

1. Extrayez le mot le plus court du tableau
2. Boucle le mot caractère par caractère
3. Vérifiez tous les mots apparaissant dans la boucle et renvoyez s'ils sont différents, et continuez s'ils ne sont pas différents

Explication

1. Vous pouvez utiliser la méthode min pour obtenir l'élément avec le plus petit nombre de caractères dans le tableau.
2. Cela peut être une instruction for ou autre.
3. return utilise des tranches. Vous pouvez couper dans la plage spécifiée avec le tableau [: nombre].

--Code de réponse

def longestCommonPrefix(self, strs):
    """
    :type strs: List[str]
    :rtype: str
    """
    if not strs:
        return ""
    shortest = min(strs,key=len)
    for i, ch in enumerate(shortest):
        for other in strs:
            if other[i] != ch:
                return shortest[:i]
    return shortest 

• Je l'écrirai aussi en Go!

func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	max := len(strs[0])

	for i := 0; i < max; i++ {
		b := strs[0][i]
		for _, str := range strs[1:] {
			if i == len(str) || b != str[i] {
				return strs[0][:i]
			}
		}
	}
	return strs[0]
}

Temps d'exécution Go et Python

À partir de la gauche, RunTime, Memory, language.