Break a string of characters of length n into a sequence of valid words. Assume that there is a data structure that tells you if a string is a valid word in constant time.
Write a program to break the words in given string.
Algorithm Explanation
![]() | Pass the combination of two strings using set to the utility function. |
![]() | If start position and string length are equal, return true. |
![]() | Otherwise, take all the words and length from the set. |
![]() | If the set contains the string in all strings set, return true. Otherwise, return false. |
Source Code
package com.dsacode.DataStructre.array; import java.util.HashSet; import java.util.Set; public class WordBreak { 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; if(end > s.length()) continue; if(s.substring(start, start+len).equals(a)) if(wordBreakHelper(s, dict, start+len)) return true; } return false; } public static void main(String[] args) { WordBreak wb = new WordBreak(); Set < String > s = new HashSet < String >(); s.add("Hello"); s.add("how"); System.out.println("Break string with 'Hello' and 'how' returns: "+ wb.wordBreak("Hellohow",s)); } }
Output
Break string with 'Hello' and 'how' returns: true