Friday, October 9, 2015

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.


No comments:

Post a Comment