| 12 | |
| 13 | /* incomplete code */ |
| 14 | public static Result parse(int wordStart, int wordEnd, Hashtable<Integer, Result> cache) { |
| 15 | if (wordEnd >= sentence.length()) { |
| 16 | return new Result(wordEnd - wordStart, sentence.substring(wordStart).toUpperCase()); |
| 17 | } |
| 18 | if (cache.containsKey(wordStart)) { |
| 19 | return cache.get(wordStart).clone(); |
| 20 | } |
| 21 | String currentWord = sentence.substring(wordStart, wordEnd + 1); |
| 22 | boolean validPartial = dictionary.contains(currentWord, false); |
| 23 | boolean validExact = validPartial && dictionary.contains(currentWord, true); |
| 24 | |
| 25 | /* break current word */ |
| 26 | Result bestExact = parse(wordEnd + 1, wordEnd + 1, cache); |
| 27 | if (validExact) { |
| 28 | bestExact.parsed = currentWord + " " + bestExact.parsed; |
| 29 | } else { |
| 30 | bestExact.invalid += currentWord.length(); |
| 31 | bestExact.parsed = currentWord.toUpperCase() + " " + bestExact.parsed; |
| 32 | } |
| 33 | |
| 34 | /* extend current word */ |
| 35 | Result bestExtend = null; |
| 36 | if (validPartial) { |
| 37 | bestExtend = parse(wordStart, wordEnd + 1, cache); |
| 38 | } |
| 39 | |
| 40 | /* find best */ |
| 41 | Result best = Result.min(bestExact, bestExtend); |
| 42 | cache.put(wordStart, best.clone()); |
| 43 | return best; |
| 44 | } |
| 45 | |
| 46 | public static int parseOptimized(int wordStart, int wordEnd, Hashtable<Integer, Integer> cache) { |
| 47 | if (wordEnd >= sentence.length()) { |