Dada una cadena sy un diccionario de palabras dict, determine si s se puede segmentar en una secuencia separada por espacios de una o más palabras del diccionario.
Por ejemplo, dado
s = «código de acceso»,
dict = [«leet», «code»].Devuelve verdadero porque «leetcode» se puede segmentar como «leet code».
1. Enfoque ingenuo
Este problema puede resolverse utilizando un enfoque ingenuo, que es trivial. Sin embargo, una discusión siempre puede comenzar a partir de ahí.
public class Solution { public boolean wordBreak(String s, Set<String> dict) { return wordBreakHelper(s, dict, 0); } public boolean wordBreakHelper(String s, Set<String> dict, int start){ if(start == s.length()) return true; for(String a: dict){ int len = a.length(); int end = start+len; //end index should be <= string length if(end > s.length()) continue; if(s.substring(start, start+len).equals(a)) if(wordBreakHelper(s, dict, start+len)) return true; } return false; } } |
El tiempo es O (n ^ 2) y excede el límite de tiempo.
2. Programación dinámica
La clave para resolver este problema mediante el uso de un enfoque de programación dinámica:
- Definir una matriz t[] tal que t[i]== true => 0- (i-1) se puede segmentar usando el diccionario
- Estado inicial t[0] == verdadero
public class Solution { public boolean wordBreak(String s, Set<String> dict) { boolean[] t = new boolean[s.length()+1]; t[0] = true; //set first to be true, why? //Because we need initial state for(int i=0; i<s.length(); i++){ //should continue from match position if(!t[i]) continue; for(String a: dict){ int len = a.length(); int end = i + len; if(end > s.length()) continue; if(t[end]) continue; if(s.substring(i, end).equals(a)){ t[end] = true; } } } return t[s.length()]; } } |
Hora: O (longitud de la cadena * tamaño del dictado).
3. Java Solution 3: simple y eficiente
En la Solución 2, si el tamaño del diccionario es muy grande, el tiempo es malo. En cambio, podemos resolver el problema en O (n ^ 2) tiempo (n es la longitud de la cadena).
public boolean wordBreak(String s, Set<String> wordDict) { int[] pos = new int[s.length()+1]; Arrays.fill(pos, -1); pos[0]=0; for(int i=0; i<s.length(); i++){ if(pos[i]!=-1){ for(int j=i+1; j<=s.length(); j++){ String sub = s.substring(i, j); if(wordDict.contains(sub)){ pos[j]=i; } } } } return pos[s.length()]!=-1; } |
4. El problema más interesante
La solución dinámica puede decirnos si la cadena se puede dividir en palabras, pero no puede decirnos en qué palabras se divide la cadena. Entonces, ¿cómo conseguir esas palabras?
Echa un vistazo a Word Break II.
