当前位置：网站首页>Leetcode 139. Mot break word Split (medium)

Leetcode 139. Mot break word Split (medium)

2022-06-24 15:41:00 【Okokabcd】

Un.、Objet

Étiquettes: Planification dynamique

Je te donne une chaîne. s Et une liste de chaînes wordDict Comme dictionnaire.Jugez si vous pouvez utiliser les mots qui apparaissent dans le dictionnaire pour assembler s .

Attention!：Tous les mots du dictionnaire ne sont pas requis,Et les mots du dictionnaire peuvent être réutilisés.

Exemple 1：

Entrée: s = "leetcode", wordDict = ["leet", "code"]
Produits: true
Explication: Retour true Parce que "leetcode" Peut être "leet" Et "code" Split into.

Exemple 2：

Entrée: s = "applepenapple", wordDict = ["apple", "pen"]
Produits: true
Explication: Retour true Parce que "applepenapple" Peut être "apple" "pen" "apple" Split into.
Attention!,Vous pouvez réutiliser les mots du Dictionnaire.

Exemple 3：

Entrée: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Produits: false

Conseils：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s Et wordDict[i] Composé uniquement de petites lettres anglaises
wordDict Toutes les chaînes dans Ils sont différents les uns des autres

2.、Comment résoudre le problème

Les conditions de segmentation de ce problème sont déterminées par la chaîne dans l'ensemble , Donc, en considérant chaque position de division , Besoin de traverser la collection de chaînes , Pour déterminer si la position actuelle peut être divisée avec succès , Attention à la position 0, La valeur d'initialisation requise est vraie .

Trois、Comment résoudre le problème

3.1 JavaRéalisation

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (String tmp : wordDict) {
                int len = tmp.length();
                if (i>=len && tmp.equals(s.substring(i - len, i))) {
                    dp[i] = dp[i] || dp[i - len];
                }
            }
        }
        return dp[n];
    }
}