Let Code Day 88 "139. Word Break" à partir de zéro

Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.

Apparemment, de nombreux ingénieurs prennent des mesures sur le site appelé LetCode.

C'est un site qui forme la puissance algorithmique qui peut résister au test de codage effectué au début de l'histoire, et c'est une voie inévitable pour ceux qui veulent faire carrière dans une entreprise de technologie à l'étranger.

Je l'ai écrit en grand, mais je n'ai pas l'intention d'avoir une telle interview pour le moment.

Cependant, en tant qu'ingénieur informatique, il serait préférable d'avoir le même niveau de puissance d'algorithme qu'un être humain, donc j'aimerais résoudre le problème de manière irrégulière et écrire la méthode que je pensais à l'époque sous forme de mémo.

Leetcode

Je le résolve avec Python3.

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day87 à partir de zéro "1512. Nombre de bonnes paires"

Twitter Je le fais.

** Blog technique Commencé! !! ** ** Je pense que la technologie écrira sur LetCode, Django, Nuxt, etc. ** C'est plus rapide à mettre à jour **, merci pour votre coopération!

problème

139. Word Break Le niveau de difficulté est moyen. Ceci est un extrait de Leet Code 60 Questions que je veux résoudre pour la préparation des entrevues de codage.

Le problème est que, étant donné une chaîne non vide «s» et un dictionnaire «wordDict» contenant une liste de mots non vides, le «s» est dans une séquence séparée par des espaces d'un ou plusieurs mots du dictionnaire. Il s'agit de déterminer s'il peut être divisé.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: false

Solution

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [True]
        for i in range(1,len(s)+1):
            for j in wordDict:
                if i >= len(j) and s[i-len(j):i] == j and dp[i-len(j)] == True:
                    dp.append(True)
                    break
            if len(dp) <= i:
                dp.append(False)
        return dp[-1]
# Runtime: 28 ms, faster than 98.48% of Python3 online submissions for Word Break.
# Memory Usage: 14 MB, less than 36.33% of Python3 online submissions for Word Break.

Puisqu'il s'agissait d'un problème DP courant, j'ai écrit qu'il renverrait True si les conditions étaient remplies. Je pense qu'il est plus important de pouvoir conditionner correctement que d'être un problème extrêmement difficile.

Mais que faire si DP rencontre un problème? Comment était-ce? Suis-je le seul à avoir tendance à être à côté de moi? Je pense que c'est une question de réflexion plutôt qu'un algorithme.

J'ai le désir de résoudre le problème relativement bien, donc ce serait bien si un tel projet pouvait être réalisé quelque part.

Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.