Word Break in Java

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