139. Séparation des mots

Plat zzu 2022-06-23 15:47:19 阅读数:512

parationdesmots

Pour toiString s Et unListe des 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

Penser

DéfinitiondpSignification du tableau et de son indice

dp[i]:ReprésentationwordDictAvant1-iLes lettres peuvent - elles être composées de mots

  • dp[i] =1 ,Avant de représenter1-i Les lettres peuvent être composées de mots
  • dp[i] = 0,Au contraire

InitialisationdpTableau

Créationdp[ s.length + 1]Tableau

Ordredp[ 0 ] =1;

Ici.dp[0] C'est auxiliaire. , Le but principal est de dp[i-word.lenth] ,Lei =word.lengthHeure,dp = 1;

Équation de transfert d'état

Ici, sidp[i-word.length] = 1, Et les mots coupés et wordMême chose.dp[i]=1

class Solution {

public boolean wordBreak(String s, List<String> wordDict) {

// step 1 CréationdpTableau
int[] dp=new int[s.length()+1];
// step 2 InitialisationdpTableau
dp[0] =1;
// step 3 Parfait.dpTableau
for (int i=1;i<dp.length;i++){

for (String word : wordDict) {

if(i>=word.length()){

if (dp[i-word.length()]==0) continue;
String sub=s.substring(i-word.length(),i);
if(sub.equals(word)) {

dp[i]=1;
break;
}
}
}
}
// step 4 printDp
for (int i = 0; i < dp.length; i++) {

System.out.println("dp "+i+","+dp[i]);
}
if (dp[dp.length-1]==1) return true;
else return false;
}
}
Copyright:Cet article est[Plat zzu]Établi,Veuillez apporter le lien original pour réimprimer,remercier。 https://fra.fheadline.com/2022/174/202206231505374165.html