Word Break Problem
The Word Break Problem is a classic challenge in computer science that deals with efficiently segmenting a given string into meaningful words using a predefined collection of words. The goal is to find all possible combinations of words from the collection that can form the original input string. This problem finds applications in text processing, natural language processing, and dictionary-based parsing.
Problem Statement
Given a collection of words and a target string, the Word Break Problem involves determining all possible ways to break down the target string into meaningful words from the collection. For instance, given the collection ["time", "to", "code"] and the string can be.
t ime t o w r i t e co de
t ime t o w r i t e code
t ime t o write co de
t ime t o write code
t ime to w r i t e co de
t ime to w r i t e code
t ime to write co de
t ime to write code
time t o w r i t e co de
time t o w r i t e code
time t o write co de
time t o write code
time to w r i t e co de
time to w r i t e code
time to write co de
time to write code
Example
Let's take the string "ilovetocode" and a collection containing words ["i", "love", "to", "code"]. The task is to break down the string using words from the collection.
Idea to Solve
The problem can be solved using a recursive approach. We iterate through the target string, checking prefixes of varying lengths. If a prefix matches a word from the collection, we recursively explore the remaining part of the string, repeating the process.
Pseudocode
function wordBreak(collection, size, str, output):
if str.length == 0:
print(output)
else:
for i from 1 to str.length:
prefix = str.substring(0, i)
for j from 0 to size:
if collection[j] == prefix:
wordBreak(collection, size, str.substring(i), output + " " + prefix)
Algorithm Explanation
- The function
wordBreak
takes the collection of words, its size, the target stringstr
, and the current output as arguments. - If the
str
is empty, we've found a valid combination, so we print theoutput
. - Otherwise, we iterate through all possible prefixes of the
str
. - For each prefix, we compare it with every word in the collection.
- If a match is found, we recursively call
wordBreak
with the remaining part of the string and the updated output. - The process continues until all possible combinations are explored.
Code Solution
// C Program
// Word Break Problem
#include <iostream>
#include <string.h>
using namespace std;
//Perform the word break of given collection and string
void word_break(const char *collection[], int size, string str, string output)
{
if (str.size() == 0)
{
//When we get result
cout << output << endl;
}
else
{
//Loop controlling variable
int i = 1;
int j = 0;
for (i; i <= str.size(); i++)
{
// Get all prefixes of current string
string prefix = str.substr(0, i);
// Check that given collection are exist prefix or not
for (j = 0; j < size; ++j)
{
//
string temp = collection[j];
if (temp.compare(prefix) == 0)
{
//Recursively execute function
word_break(collection, size, str.substr(i), output + " " + prefix);
}
}
}
}
}
int main()
{
//Define collection of text
const char *collection[] = {
"t" , "ime" , "to" , "code" , "hi" , "s" , "o" , "w" , "r" , "time" , "i" , "e" , "life" , "co" , "de" , "write"
};
//Get the size of collection element
int size = sizeof(collection) / sizeof(collection[0]);
//Define string
string word = "timetowritecode";
word_break(collection, size, word, "");
return 0;
}
Output
t ime t o w r i t e co de
t ime t o w r i t e code
t ime t o write co de
t ime t o write code
t ime to w r i t e co de
t ime to w r i t e code
t ime to write co de
t ime to write code
time t o w r i t e co de
time t o w r i t e code
time t o write co de
time t o write code
time to w r i t e co de
time to w r i t e code
time to write co de
time to write code
// Java program
// Word Break Problem
class WordBreak
{
//Perform the word break of given collection and string
public void word_break(String []collection, String text, String output)
{
if (text.length() == 0)
{
//When we get result
System.out.print("\n"+output);
}
else
{
//Loop controlling variable
int i = 0;
int j = 0;
String prefix = "";
for (i=1; i <= text.length(); i++)
{
// Get all prefixes of current string
prefix = text.substring(0, i);
// Check that given collection are exist prefix or not
for (j = 0; j < collection.length; ++j)
{
if (collection[j].equals(prefix))
{
//Recursively execute function
word_break(collection, text.substring(i), output + " " + prefix);
}
}
}
}
}
public static void main(String[] args)
{
WordBreak obj = new WordBreak();
//Define collection of text
String[] collection = {
"t",
"ime",
"to",
"code",
"hi",
"s",
"o",
"w",
"r",
"time",
"i",
"e",
"life",
"co",
"de",
"write"
};
//Define string
String word = "timetowritecode";
obj.word_break(collection, word, "");
}
}
Output
t ime t o w r i t e co de
t ime t o w r i t e code
t ime t o write co de
t ime t o write code
t ime to w r i t e co de
t ime to w r i t e code
t ime to write co de
t ime to write code
time t o w r i t e co de
time t o w r i t e code
time t o write co de
time t o write code
time to w r i t e co de
time to w r i t e code
time to write co de
time to write code
//Include namespace system
using System;
// C# program
// Word Break Problem
class WordBreak
{
//Perform the word break of given collection and string
public void word_break(String[] collection, String text, String output)
{
if (text.Length == 0)
{
//When we get result
Console.Write("\n" + output);
}
else
{
//Loop controlling variable
int i = 0;
int j = 0;
String prefix = "";
for (i = 1; i <= text.Length; i++)
{
// Get all prefixes of current string
prefix = text.Substring(0, i);
// Check that given collection are exist prefix or not
for (j = 0; j < collection.Length; ++j)
{
if (collection[j].Equals(prefix))
{
//Recursively execute function
word_break(collection, text.Substring(i), output + " " + prefix);
}
}
}
}
}
public static void Main(String[] args)
{
WordBreak obj = new WordBreak();
//Define collection of text
String[] collection = {
"t" , "ime" , "to" , "code" , "hi" , "s" , "o" , "w" , "r" , "time" , "i" , "e" , "life" , "co" , "de" , "write"
};
//Define string
String word = "timetowritecode";
obj.word_break(collection, word, "");
}
}
Output
t ime t o w r i t e co de
t ime t o w r i t e code
t ime t o write co de
t ime t o write code
t ime to w r i t e co de
t ime to w r i t e code
t ime to write co de
t ime to write code
time t o w r i t e co de
time t o w r i t e code
time t o write co de
time t o write code
time to w r i t e co de
time to w r i t e code
time to write co de
time to write code
<?php
// Php program
// Word Break Problem
class WordBreak
{
//Perform the word break of given collection and string
public function word_break( & $collection, $text, $output)
{
if (strlen($text) == 0)
{
//When we get result
echo "\n". $output;
}
else
{
//Loop controlling variable
$i = 0;
$j = 0;
$prefix = "";
for ($i = 1; $i <= strlen($text); $i++)
{
// Get all prefixes of current string
$prefix = substr($text,0, $i);
// Check that given collection are exist prefix or not
for ($j = 0; $j < count($collection); ++$j)
{
if ($collection[$j]==($prefix))
{
//Recursively execute function
$this->word_break($collection, substr($text,$i), $output ." ". $prefix);
}
}
}
}
}
}
function main()
{
$obj = new WordBreak();
//Define collection of text
$collection = array("t", "ime", "to", "code", "hi", "s", "o", "w", "r", "time", "i", "e", "life", "co", "de", "write");
//Define string
$word = "timetowritecode";
$obj->word_break($collection, $word, "");
}
main();
Output
t ime t o w r i t e co de
t ime t o w r i t e code
t ime t o write co de
t ime t o write code
t ime to w r i t e co de
t ime to w r i t e code
t ime to write co de
t ime to write code
time t o w r i t e co de
time t o w r i t e code
time t o write co de
time t o write code
time to w r i t e co de
time to w r i t e code
time to write co de
time to write code
// Node Js program
// Word Break Problem
class WordBreak
{
//Perform the word break of given collection and string
word_break(collection, text, output)
{
if (text.length == 0)
{
//When we get result
console.log(output);
}
else
{
//Loop controlling variable
var i = 0;
var j = 0;
var prefix = "";
for (i = 1; i <= text.length; i++)
{
// Get all prefixes of current string
prefix = text.substring(0, i);
// Check that given collection are exist prefix or not
for (j = 0; j < collection.length; ++j)
{
if (collection[j]==(prefix))
{
//Recursively execute function
this.word_break(collection, text.substring(i), output + " " + prefix);
}
}
}
}
}
}
function main()
{
var obj = new WordBreak();
//Define collection of text
var collection = ["t", "ime", "to", "code", "hi", "s", "o", "w", "r", "time", "i", "e", "life", "co", "de", "write"];
//Define string
var word = "timetowritecode";
obj.word_break(collection, word, "");
}
main();
Output
t ime t o w r i t e co de
t ime t o w r i t e code
t ime t o write co de
t ime t o write code
t ime to w r i t e co de
t ime to w r i t e code
t ime to write co de
t ime to write code
time t o w r i t e co de
time t o w r i t e code
time t o write co de
time t o write code
time to w r i t e co de
time to w r i t e code
time to write co de
time to write code
# Python 3 program
# Word Break Problem
class WordBreak :
# Perform the word break of given collection and string
def word_break(self, collection, text, output) :
if (len(text) == 0) :
# When we get result
print("\n", output, end = "")
else :
# Loop controlling variable
i = 1
j = 0
prefix = ""
while (i <= len(text)) :
# Get all prefixes of current string
prefix = text[:i]
# Check that given collection are exist prefix or not
j = 0
while (j < len(collection)) :
if (collection[j]==(prefix)) :
# Recursively execute function
self.word_break(collection, text[i:], output +" "+ prefix)
j += 1
i += 1
def main() :
obj = WordBreak()
# Define collection of text
collection = ["t", "ime", "to", "code", "hi", "s", "o", "w", "r", "time", "i", "e", "life", "co", "de", "write"]
# Define string
word = "timetowritecode"
obj.word_break(collection, word, "")
if __name__ == "__main__": main()
Output
t ime t o w r i t e co de
t ime t o w r i t e code
t ime t o write co de
t ime t o write code
t ime to w r i t e co de
t ime to w r i t e code
t ime to write co de
t ime to write code
time t o w r i t e co de
time t o w r i t e code
time t o write co de
time t o write code
time to w r i t e co de
time to w r i t e code
time to write co de
time to write code
# Ruby program
# Word Break Problem
class WordBreak
# Perform the word break of given collection and string
def word_break(collection, text, output)
if (text.length() == 0)
# When we get result
print("\n", output)
else
# Loop controlling variable
i = 1
j = 0
prefix = ""
while (i <= text.length())
# Get all prefixes of current string
prefix = text[0, i]
# Check that given collection are exist prefix or not
j = 0
while (j < collection.length)
if (collection[j]==(prefix))
# Recursively execute function
self.word_break(collection, text[i..text.length], output +" "+ prefix)
end
j += 1
end
i += 1
end
end
end
end
def main()
obj = WordBreak.new()
# Define collection of text
collection = ["t", "ime", "to", "code", "hi", "s", "o", "w", "r", "time", "i", "e", "life", "co", "de", "write"]
# Define string
word = "timetowritecode"
obj.word_break(collection, word, "")
end
main()
Output
t ime t o w r i t e co de
t ime t o w r i t e code
t ime t o write co de
t ime t o write code
t ime to w r i t e co de
t ime to w r i t e code
t ime to write co de
t ime to write code
time t o w r i t e co de
time t o w r i t e code
time t o write co de
time t o write code
time to w r i t e co de
time to w r i t e code
time to write co de
time to write code
// Scala program
// Word Break Problem
class WordBreak
{
//Perform the word break of given collection and string
def word_break(collection: Array[String], text: String, output: String): Unit = {
if (text.length() == 0)
{
//When we get result
print("\n" + output);
}
else
{
//Loop controlling variable
var i: Int = 1;
var j: Int = 0;
var prefix: String = "";
while (i <= text.length())
{
// Get all prefixes of current string
prefix = text.substring(0, i);
// Check that given collection are exist prefix or not
j = 0;
while (j < collection.length)
{
if (collection(j).equals(prefix))
{
//Recursively execute function
word_break(collection, text.substring(i), output + " " + prefix);
}
j += 1;
}
i += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: WordBreak = new WordBreak();
//Define collection of text
var collection: Array[String] = Array("t", "ime", "to", "code", "hi", "s", "o", "w", "r", "time", "i", "e", "life", "co", "de", "write");
//Define string
var word: String = "timetowritecode";
obj.word_break(collection, word, "");
}
}
Output
t ime t o w r i t e co de
t ime t o w r i t e code
t ime t o write co de
t ime t o write code
t ime to w r i t e co de
t ime to w r i t e code
t ime to write co de
t ime to write code
time t o w r i t e co de
time t o w r i t e code
time t o write co de
time t o write code
time to w r i t e co de
time to w r i t e code
time to write co de
time to write code
// Swift program
// Word Break Problem
import Foundation
class WordBreak
{
func get_prefix(_ text: [Character],_ size : Int) -> String
{
var result : String = "";
var i = 0;
while(i<size)
{
result += String(text[i]);
i = i+1;
}
return result;
}
func get_suffix(_ text : [Character],_ start : Int,_ size : Int) -> String
{
var result : String = "";
var i = start;
while(i<size)
{
result += String(text[i]);
i = i+1;
}
return result;
}
//Perform the word break of given collection and string
func word_break(_ collection: [String], _ text: String, _ output: String)
{
if (text.count == 0)
{
//When we get result
print( output, terminator: "\n");
}
else
{
//Loop controlling variable
var i: Int = 1;
var j: Int = 0;
var prefix: String = "";
let data = Array(text);
while (i <= text.count)
{
// Get all prefixes of current string
prefix = get_prefix(data,i)
// Check that given collection are exist prefix or not
j = 0;
while (j < collection.count)
{
if (collection[j]==(prefix))
{
//Recursively execute function
self.word_break(collection, get_suffix(data,i,data.count), output + " " + prefix);
}
j += 1;
}
i += 1;
}
}
}
}
func main()
{
let obj: WordBreak = WordBreak();
//Define collection of text
let collection: [String] = ["t", "ime", "to", "code", "hi", "s", "o", "w", "r", "time", "i", "e", "life", "co", "de", "write"];
//Define string
let word: String = "timetowritecode";
obj.word_break(collection, word, "");
}
main();
Output
t ime t o w r i t e co de
t ime t o w r i t e code
t ime t o write co de
t ime t o write code
t ime to w r i t e co de
t ime to w r i t e code
t ime to write co de
t ime to write code
time t o w r i t e co de
time t o w r i t e code
time t o write co de
time t o write code
time to w r i t e co de
time to w r i t e code
time to write co de
time to write code
Time Complexity
The time complexity of the algorithm can be analyzed in terms of the number of recursive calls made. In the worst case, each prefix might be matched with all words in the collection, resulting in a time complexity of O(n^2 * m), where n is the length of the input string and m is the size of the collection.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment