Posted on by Kalkicode
Code Dynamic Programming

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

  1. The function wordBreak takes the collection of words, its size, the target string str, and the current output as arguments.
  2. If the str is empty, we've found a valid combination, so we print the output.
  3. Otherwise, we iterate through all possible prefixes of the str.
  4. For each prefix, we compare it with every word in the collection.
  5. If a match is found, we recursively call wordBreak with the remaining part of the string and the updated output.
  6. 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.

Comment

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





Categories
Relative Post