| 44 | } |
| 45 | |
| 46 | public static int parseOptimized(int wordStart, int wordEnd, Hashtable<Integer, Integer> cache) { |
| 47 | if (wordEnd >= sentence.length()) { |
| 48 | return wordEnd - wordStart; |
| 49 | } |
| 50 | if (cache.containsKey(wordStart)) { |
| 51 | return cache.get(wordStart); |
| 52 | } |
| 53 | |
| 54 | String currentWord = sentence.substring(wordStart, wordEnd + 1); |
| 55 | boolean validPartial = dictionary.contains(currentWord, false); |
| 56 | |
| 57 | /* break current word */ |
| 58 | int bestExact = parseOptimized(wordEnd + 1, wordEnd + 1, cache); |
| 59 | if (!validPartial || !dictionary.contains(currentWord, true)) { |
| 60 | bestExact += currentWord.length(); |
| 61 | } |
| 62 | |
| 63 | /* extend current word */ |
| 64 | int bestExtend = Integer.MAX_VALUE; |
| 65 | if (validPartial) { |
| 66 | bestExtend = parseOptimized(wordStart, wordEnd + 1, cache); |
| 67 | } |
| 68 | |
| 69 | /* find best */ |
| 70 | int min = Math.min(bestExact, bestExtend); |
| 71 | cache.put(wordStart, min); |
| 72 | return min; |
| 73 | } |
| 74 | |
| 75 | public static int parseSimple(int wordStart, int wordEnd) { |
| 76 | if (wordEnd >= sentence.length()) { |