Dada una oración válida sin espacios entre las palabras y un diccionario de palabras válidas en inglés, encuentre todas las formas posibles de dividir la oración en palabras individuales del diccionario.
Ejemplo:
Consider the following dictionary
{ i, like, sam, sung, samsung, mobile, ice,
and, cream, icecream, man, go, mango}
Input: "ilikesamsungmobile"
Output: i like sam sung mobile
i like samsung mobile
Input: "ilikeicecreamandmango"
Output: i like ice cream and man go
i like ice cream and mango
i like icecream and man go
i like icecream and mango
Hemos discutido una solución de programación dinámica en la publicación a continuación.
Programación Dinámica | Serie 32 (Problema de separación de palabras)
La solución de Programación Dinámica solo encuentra si es posible romper una palabra o no. Aquí necesitamos imprimir todos los posibles saltos de palabras.
Comenzamos a escanear la oración desde la izquierda. A medida que encontramos una palabra válida, debemos verificar si el resto de la oración puede formar palabras válidas o no. Porque en algunas situaciones, la primera palabra encontrada del lado izquierdo puede dejar una porción restante que no se puede separar más. Entonces, en ese caso, deberíamos regresar y dejar la palabra encontrada actualmente y seguir buscando la siguiente palabra. Y este proceso es recursivo porque para saber si la porción correcta es separable o no, necesitamos la misma lógica. Así que usaremos la recursividad y el retroceso para resolver este problema. Para realizar un seguimiento de las palabras encontradas, utilizaremos una pila. Siempre que la parte derecha de la string no forme palabras válidas, extraemos la string superior de la pila y continuamos buscando.
A continuación se muestra la implementación de la idea anterior:
C++
// A recursive program to print all possible
// partitions of a given string into dictionary
// words
#include <iostream>
using namespace std;
/* A utility function to check whether a word
is present in dictionary or not. An array of
strings is used for dictionary. Using array
of strings for dictionary is definitely not
a good idea. We have used for simplicity of
the program*/
int dictionaryContains(string &word)
{
string dictionary[] = {"mobile","samsung","sam","sung",
"man","mango", "icecream","and",
"go","i","love","ice","cream"};
int n = sizeof(dictionary)/sizeof(dictionary[0]);
for (int i = 0; i < n; i++)
if (dictionary[i].compare(word) == 0)
return true;
return false;
}
// Prototype of wordBreakUtil
void wordBreakUtil(string str, int size, string result);
// Prints all possible word breaks of given string
void wordBreak(string str)
{
// Last argument is prefix
wordBreakUtil(str, str.size(), "");
}
// Result store the current prefix with spaces
// between words
void wordBreakUtil(string str, int n, string result)
{
//Process all prefixes one by one
for (int i=1; i<=n; i++)
{
// Extract substring from 0 to i in prefix
string prefix = str.substr(0, i);
// If dictionary contains this prefix, then
// we check for remaining string. Otherwise
// we ignore this prefix (there is no else for
// this if) and try next
if (dictionaryContains(prefix))
{
// If no more elements are there, print it
if (i == n)
{
// Add this element to previous prefix
result += prefix;
cout << result << endl;
return;
}
wordBreakUtil(str.substr(i, n-i), n-i,
result + prefix + " ");
}
}
}
//Driver Code
int main()
{
// Function call
cout << "First Test:\n";
wordBreak("iloveicecreamandmango");
cout << "\nSecond Test:\n";
wordBreak("ilovesamsungmobile");
return 0;
}
Java
// A recursive program to print all possible
// partitions of a given string into dictionary
// words
import java.io.*;
import java.util.*;
class GFG {
// Prints all possible word breaks of given string
static void wordBreak(int n, List<String> dict, String s)
{
String ans="";
wordBreakUtil(n, s, dict, ans);
}
static void wordBreakUtil(int n, String s, List<String> dict, String ans)
{
for(int i = 1; i <= n; i++)
{
// Extract substring from 0 to i in prefix
String prefix=s.substring(0, i);
// If dictionary contains this prefix, then
// we check for remaining string. Otherwise
// we ignore this prefix (there is no else for
// this if) and try next
if(dict.contains(prefix))
{
// If no more elements are there, print it
if(i == n)
{
// Add this element to previous prefix
ans += prefix;
System.out.println(ans);
return;
}
wordBreakUtil(n - i, s.substring(i,n), dict, ans+prefix+" ");
}
}
}
// main function
public static void main(String args[])
{
String str1 = "iloveicecreamandmango"; // for first test case
String str2 ="ilovesamsungmobile"; // for second test case
int n1 = str1.length(); // length of first string
int n2 = str2.length(); // length of second string
// List of strings in dictionary
List <String> dict= Arrays.asList("mobile","samsung","sam","sung",
"man","mango", "icecream","and",
"go","i","love","ice","cream");
System.out.println("First Test:");
// call to the method
wordBreak(n1,dict,str1);
System.out.println("\nSecond Test:");
// call to the method
wordBreak(n2,dict,str2);
}
}
// This code is contributed by mohitjha727.
Python3
# A recursive program to print all possible
# partitions of a given string into dictionary
# words
# A utility function to check whether a word
# is present in dictionary or not. An array of
# strings is used for dictionary. Using array
# of strings for dictionary is definitely not
# a good idea. We have used for simplicity of
# the program
def dictionaryContains(word):
dictionary = {"mobile", "samsung", "sam", "sung", "man",
"mango", "icecream", "and", "go", "i", "love", "ice", "cream"}
return word in dictionary
# Prints all possible word breaks of given string
def wordBreak(string):
# Last argument is prefix
wordBreakUtil(string, len(string), "")
# Result store the current prefix with spaces
# between words
def wordBreakUtil(string, n, result):
# Process all prefixes one by one
for i in range(1, n + 1):
# Extract substring from 0 to i in prefix
prefix = string[:i]
# If dictionary contains this prefix, then
# we check for remaining string. Otherwise
# we ignore this prefix (there is no else for
# this if) and try next
if dictionaryContains(prefix):
# If no more elements are there, print it
if i == n:
# Add this element to previous prefix
result += prefix
print(result)
return
wordBreakUtil(string[i:], n - i, result+prefix+" ")
# Driver Code
if __name__ == "__main__":
print("First Test:")
wordBreak("iloveicecreamandmango")
print("\nSecond Test:")
wordBreak("ilovesamsungmobile")
# This code is contributed by harshitkap00r
C#
// A recursive program to print all possible
// partitions of a given string into dictionary
// words
using System;
using System.Collections.Generic;
class GFG {
// Prints all possible word breaks of given string
static void wordBreak(int n, List<string> dict, string s)
{
string ans="";
wordBreakUtil(n, s, dict, ans);
}
static void wordBreakUtil(int n, string s, List<string> dict, string ans)
{
for(int i = 1; i <= n; i++)
{
// Extract substring from 0 to i in prefix
string prefix=s.Substring(0, i);
// If dictionary contains this prefix, then
// we check for remaining string. Otherwise
// we ignore this prefix (there is no else for
// this if) and try next
if(dict.Contains(prefix))
{
// If no more elements are there, print it
if(i == n)
{
// Add this element to previous prefix
ans += prefix;
Console.WriteLine(ans);
return;
}
wordBreakUtil(n - i, s.Substring(i,n-i), dict, ans+prefix+" ");
}
}
}
static void Main() {
string str1 = "iloveicecreamandmango"; // for first test case
string str2 ="ilovesamsungmobile"; // for second test case
int n1 = str1.Length; // length of first string
int n2 = str2.Length; // length of second string
// List of strings in dictionary
List<string> dict= new List<string>(new string[]{"mobile","samsung","sam","sung",
"man","mango", "icecream","and",
"go","i","love","ice","cream"});
Console.WriteLine("First Test:");
// call to the method
wordBreak(n1,dict,str1);
Console.WriteLine();
Console.WriteLine("Second Test:");
// call to the method
wordBreak(n2,dict,str2);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// A recursive program to print all possible
// partitions of a given string into dictionary
// words
// Prints all possible word breaks of given string
function wordBreak(n,dict,s)
{
let ans="";
wordBreakUtil(n, s, dict, ans);
}
function wordBreakUtil(n,s,dict,ans)
{
for(let i = 1; i <= n; i++)
{
// Extract substring from 0 to i in prefix
let prefix=s.substring(0, i);
// If dictionary contains this prefix, then
// we check for remaining string. Otherwise
// we ignore this prefix (there is no else for
// this if) and try next
if(dict.includes(prefix))
{
// If no more elements are there, print it
if(i == n)
{
// Add this element to previous prefix
ans += prefix;
document.write(ans+"<br>");
return;
}
wordBreakUtil(n - i, s.substring(i,n), dict, ans+prefix+" ");
}
}
}
// main function
let str1 = "iloveicecreamandmango"; // for first test case
let str2 ="ilovesamsungmobile"; // for second test case
let n1 = str1.length; // length of first string
let n2 = str2.length; // length of second string
// List of strings in dictionary
let dict= ["mobile","samsung","sam","sung",
"man","mango", "icecream","and",
"go","i","love","ice","cream"];
document.write("First Test:<br>");
// call to the method
wordBreak(n1,dict,str1);
document.write("<br>Second Test:<br>");
// call to the method
wordBreak(n2,dict,str2);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
First Test: i love ice cream and man go i love ice cream and mango i love icecream and man go i love icecream and mango Second Test: i love sam sung mobile i love samsung mobile
Complejidades:
- Complejidad temporal : O(2 n ). Porque hay 2 n combinaciones en The Worst Case.
- Espacio Auxiliar : O(n 2 ). Debido a la función Recursive Stack of wordBreakUtil(…) en el peor de los casos.
Donde n es la longitud de la string de entrada.
Este artículo es una contribución de Raghav Jajodia . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA