Break String into Dictionary Words

Given an English dictionary (implemented as a hashmap (word -> meaning)) and a string without spaces, output all possible combinations of valid English words that when combined, reproduce the input string.

e.g. input: “programmerit”
output: {{pro, gram, merit}, {program, merit}, {programmer, it}}
output:

Solution:

Recursive implementation:
The idea is simple, we consider each prefix and search it in dictionary. If the prefix is present in dictionary, we recur for rest of the string (or suffix).

public static HashMap<String,String> getDictionary()
{
    HashMap<String,String> hm=new HashMap<String,String>();
    hm.put("a","a");
    hm.put("it","it");
    hm.put("am","am");
    hm.put("ram","ram");
    hm.put("pro","pro");
    hm.put("grammer","grammer");
    hm.put("program","program");
    hm.put("programmer","programmer");
    hm.put("me","me");
    hm.put("merit","merit");
    return hm;
}
 
public static void findWords(String s, int length, String out)
{
    HashMap<String,String>hm = getDictionary();
    for (int i=1; i <= length; i++)
    {
        String subwords = s.substring(0, i);
        if (hm.containsKey(subwords))
        {
            if (i == length)
            {
                out = out + subwords;
                System.out.println(out);
                return;
            }
            findWords(s.substring(i,length), length-i, out+subwords+" ");
        }
    }
}
 
public static void main (String[] args) throws java.lang.Exception
{
    String s = "programmerit";
    findWords(s,s.length(),"");
}

4 Thoughts on “Break String into Dictionary Words

  1. Pravesh Kumar on April 25, 2015 at 4:13 am said:

    What is time complexity ?? is it O(n!) ??

  2. Azra Irshad Rabbani on May 4, 2015 at 3:12 am said:

    public static void findWordsFromString(String str,int index, Set words) {
    if(index > str.length()) {
    return;
    }
    findWordsFromString(str,index+1, words);
    for(int i = 0 ; i < index; i++) {
    String sub = str.substring(i, index);
    if(isValidWord(sub)) {
    words.add(sub);
    }
    }
    }

  3. Complexity is interesting, assuming average length of word m, let’s define the average number of words, w = n/m where n is the length of the input string. At each deduction of a word from the string, (w-1) subtrees start to recurse. w * w-1 * w-2 etc.. so it’s w! or (n/m)!

  4. The complexity is o(n*n).

    Consider a string of length n, s1s2s3s4——-sn.

    There will be n sub srtings starting with s1,and (n-1) sub strings starting with s2 ……….and 1 substring starting with sn. Hence the total number of strings one need to consider is,

    (n)+(n-1)+…………+1 = n(n+1)/2 ——–> O(n*n).

    Please let me know if my analysis is wrong.

Leave a Reply to Pravesh Kumar Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation