tasty solution to word break finder

[feisty_meow.git] / kona / src / org / feistymeow / textual / WordBreakFinder.java

diff --git a/kona/src/org/feistymeow/textual/WordBreakFinder.java b/kona/src/org/feistymeow/textual/WordBreakFinder.java
new file mode 100644 (file)
index 0000000..17388a8
--- /dev/null
+++ b/kona/src/org/feistymeow/textual/WordBreakFinder.java
@@ -0,0 +1,73 @@
+package org.feistymeow.textual;
+
+import java.util.HashSet;
+import java.util.Set;
+
+public class WordBreakFinder
+{
+  public WordBreakFinder(SimpleDictionary lookups) {
+    _lookups = lookups;
+  }
+
+  public Set<String> findStringsWithGoodSpacing(String orig) {
+    HashSet<String> toReturn = new HashSet<String>();
+    int startingChunk = Math.min(orig.length(), _lookups.longestWord());
+    for (int i = startingChunk; i >= 1; i--) {
+      String first = orig.substring(0, i);
+      if (!_lookups.lookup(first)) {
+        // fail fast.  this length chunk of the word doesn't match.
+        continue;
+      }
+      String second = orig.substring(i, orig.length());
+      // first part of string is listed in dictionary.  we can trivially add it if the other part is empty.
+      if (second.length() == 0) {
+         toReturn.add(first);
+         continue;
+      }
+      Set<String> matches = findStringsWithGoodSpacing(second);
+      if (matches != null) {
+        for (String matched : matches) {
+           toReturn.add(first + " " + matched);
+        }
+      }
+    }
+    if (toReturn.isEmpty()) return null;
+    return toReturn;
+  }
+
+  SimpleDictionary _lookups;  
+
+  public static void main(String argv[]) {
+    String smallWordList[] = {
+       "hops", "barley", "malt", "beer", "turnip"
+    };
+    SimpleDictionary lookups = new SimpleDictionary(smallWordList);
+    WordBreakFinder finder = new WordBreakFinder(lookups);
+    
+    String toBreak = "maltbeerbeerturniphops";
+    Set<String> matches =  finder.findStringsWithGoodSpacing(toBreak);
+    if (matches != null) {
+      System.out.println("matches found:");
+      for (String match : matches) {
+         System.out.println(match);
+      }
+    } else {
+      System.out.println("ERROR: failed to find matches!");
+    }
+
+    toBreak = "maltbeerbeturniphops";
+    matches =  finder.findStringsWithGoodSpacing(toBreak);
+    if (matches != null) {
+      System.out.println("ERROR: matches found:");
+      for (String match : matches) {
+         System.out.println(match);
+      }
+    } else {
+      System.out.println("found no matches, which is correct.");
+    }
+  }
+
+}
+
+
+