Break compound word into multiple words

A compound word is a word which can be broken into multiple words. For example: appletree can be broken to apple and tree. Note a single word is not compound word, and a compound word may be broken into words in different ways, for example, autopay can be broken into au, to, pay, Or auto, pay.

Here we use woomom as example, and assume we have a helper function isWord(String w) which can tell us if any string is word or not.

    /*
     * woomom = woo + mom Or woom + om
     */
    static boolean isWord(String w){
        return w.equals("woom") || w.equals("woo") || w.equals("om") || w.equals("mom");
    }
   
    public static String printCompoundWord(String w){
        return printCompoundWordRec(w, 0, 0);
    }
   
    public static String printCompoundWordRec(String w, int start, int found){
        if(start == w.length()){
            return found>1?"":null;
        }
       
        for(int i=start+1; i<=w.length(); i++){
            if(isWord(w.substring(start, i))){
                String s  = printCompoundWordRec(w, i, found+1);
                if(s!=null){
                    String re = w.substring(start, i) + "-" + s;
                    if(found==0){
                        System.out.println(re);
                    }else
                        return re;
                   
                }
            }
        }
       
        return null;
    }

Here is iterative approach to check if word is compound word.

	public static boolean wordBreak(String[] dict, String str) {
	int len = str.length();
	/*
	* a boolean array, hasWord[i] indicates if there is a word in the dictionary
	* starts somewhere in the string and ends at position i
	* e.g. hasWord[len-1] mean the string is breakable
	*/
	boolean[] hasWord = new boolean[len];
	/*
	* we starts from the beginning of string, check if there is any word which starts
	* at the index i and ends at i+word_length-1, if yes, mark the i+word_length-1 to true
	*/
	for(int i=0; i<len; i++) {
	//we skip the i if there is no word ends at i-1
	if(i-1>=0 && !hasWord[i-1])
	continue;
	for(String word:dict) {
	int wLen = word.length();
	if(wLen+i<=len && str.substring(i, i+wLen).equals(word))
	hasWord[i+wLen-1] = true;
	}
	}
	return hasWord[len-1];
	}

view raw wordBreakable.java hosted with ❤ by GitHub