Recursion? Combinations in a String

Question

I've been dealing with the following recursion question for a while now and haven't been able to figure it out. Basically, you have some sort of a sentence made out of certain words, where all the words are just jammed together, not spaced out. The idea is to find the number of all possible combinations of words that can be used to create the sentence.

For example,

• Words: ook, ookook
• Sentence: ookookook
• Solution: {ook, ook, ook}, {ookook, ook}, {ook, ookook}.

Another example:

• Words: ooga, oogam, oogum, mook, ook
• Sentence: oogamookoogumook
• Solution: {ooga, mook, oogum, ook}, {oogam, ook, oogum, ook}

I've tried a lot of things, finally giving up and trying to do it manually...

public static int WAYS(String word) {
    int ways = 1;
    for (int i = 0; i < word.length(); i++) {
        try{
            if(word.substring(i, i - 2).equals("ug")){
                if(word.substring(i - 4, i - 2).equals("ug")){
                    ways++;
                }
            }
            else if(word.substring(i, i - 3).contains("ook")){
                System.out.println(word.substring(i-6, i-3));
                if(word.substring(i - 6, i - 3).equals("ook")){
                    ways++;
                }
                if(word.charAt(i - 4) == 'm'){
                    if(word.substring(i - 8, i - 4).equals("ooga") || word.substring(i - 8, i - 4).equals("oogu")){
                        ways++;
                    }
                }
            }
            else if(word.substring(i, i - 4).contains("mook")){
                if(word.substring(i - 8, i - 4).contains("mook")){
                    ways++;
                }
            }
            if(word.substring(i, i - 2).equals("oog")){
                if(word.charAt(i + 2) == 'm'){
                    if(word.charAt(i + 1) == 'a' || word.charAt(i + 1) == 'u'){
                        ways++;
                    }
                }
            }
        } catch(Exception e){
            continue;
        }
    }
    return ways;
}

But it hasn't worked. Could somebody please give me an idea or a sample on approaching this problem using recursion?

Answer 1

1. Name your methods properly, "WAYS" is a constant name, not a method name.

2. Provide runnable code, especially in cases where it's so short.

3. Never use Exceptions for control flow. (*Never say never; But unless you're actually designing some weird control flow primitives, like support for non-local returns: don't use Exceptions for control flow)

4. You are using magic values like "uug" and "ook" in your code? Does this look simple and obvious? Does this look maintainable? What is this supposed to look like if you get a lexicon with a million of different words?

Edit: giving the complete listing is somehow boring, so I left a few gaps. Try to fill those, hope that helps.

public class JammedWords {
  public static int ways(String sentence, String[] words) {
    if (sentence.isEmpty()) {
      // The trivial case: the sentence is empty. Return a single number.
    } else {
      int c = 0;
      for (String w: words) {
        if (sentence.startsWith(w)) {
          // call method recursively, update counter `c`.
        }
      }
      return c;
    }
  }
  public static void main(String[] args) {
    System.out.println(ways("ookookook", new String[]{"ook", "ookook"}));
    System.out.println(ways("oogamookoogumook", new String[]{"ooga","oogam","oogum","mook","ook"}));
  }
}

Hints:

A) Understand the difference between empty set, set containing the empty set, set containing a set containing an empty set etc. Sets that contain empty sets are of course not empty, and their size is not 0.

B) There is a handy method String.substring(n) that drops everything before the 'n'-th character. And there is String.length() to get size of words.