4
\$\begingroup\$

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<String> dict = new HashSet<String>();
        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 < right) {
            for (int i = 0; i <= right; i++) {
                String word = input.substring(i, right);
                word = word.toLowerCase();
                if (dict.contains(word)) {
                    count++;
                    right = i;
                    System.out.println(" -> " + word);
                }
            }

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

}

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

\$\endgroup\$
  • \$\begingroup\$ I had a similar question a while ago that simply ensures that a string is made out of real words, based on a dictionary, the algorithm there should also apply for your case, nl, building up a dictionary based on the first and last letter of each word in the dictionary, and thus checking if your dictionary contains such words, potentially with involving the length of a word, it makes searching for words a lot faster, maybe I could check to make it work in java :) \$\endgroup\$ – Icepickle Aug 22 '17 at 20:17
3
\$\begingroup\$

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<String> vocabulary) {
    text = text.toLowerCase();
    int left = 0;
    int right = text.length();
    List<String> result = new ArrayList<>();

    while (left < right) {
        for (int i = 0; i <= 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.