Given a String and dictionary of words, break the string in minimum space sentence Given a String and dictionary of words, break the string in minimum space sentence.

Ex: 
inputStr = "ilikefacebook" 
dictionary = {"i","like","face","book","facebook"} 
Possible Strings: 
i like face book - 3 spaces 
i like Facebook - 2 spaces - this is expected answer.


Here's a trivial solution. It's a simple solution, but the runtime performance is poor O(n2). There must be better ways of doing this. 

public class MyClass {

    public static void main(String[] args) {

        String input = "IlikeFacebook";

        HashSet&lt;String&gt; dict = new HashSet&lt;String&gt;();
        dict.add("i");
        dict.add("like");
        dict.add("face");
        dict.add("book");
        dict.add("facebook");


        int left = 0;
        int right = input.length();
        int count = -1;

        boolean[] status = new boolean[input.length()];

        while (left &lt; right) {
            for (int i = 0; i &lt;= right; i++) {
                String word = input.substring(i, right);
                word = word.toLowerCase();
                if (dict.contains(word)) {
                    count++;
                    right = i;
                    System.out.println(" -&gt; " + word);
                }
            }

        }
        System.out.println(" Space count " + count);
    }

}


Can anyone provide a better and efficient solution of this problem?
Advice 1

You can get a substantial speed up by setting input = input.toLowerCase() and removing word = word.toLowerCase().

Advice 2

What comes to code, I suggest you separate the actual algorithm from the standard output. That way you can reuse your solution on larger string without getting overwhelmed with all the output. Also, it allows passing the result to some other processing routines, etc:

public static String[] opGetShortestTokenizationV2(String text,
                                                   Set&lt;String&gt; vocabulary) {
    text = text.toLowerCase();
    int left = 0;
    int right = text.length();
    List&lt;String&gt; result = new ArrayList&lt;&gt;();

    while (left &lt; right) {
        for (int i = 0; i &lt;= right; i++) {
            String word = text.substring(i, right);
            if (vocabulary.contains(word)) {
                right = i;
                result.add(word);
            }
        }
    }

    Collections.reverse(result);
    return result.toArray(new String[result.size()]);
}


Advice 3

left is not used. Your while loop condition becomes right != 0.