Friday, March 29, 2013

word segment from a string.

Given an input string and a dictionary of words, implement a method that breaks up the input string into a space-separated string of dictionary words that a search engine might use for "Did you mean?" For example, an input of "applepie" should yield an output of "apple pie".

A back tracking solution would produce O(2^n) complexity. An efficient solution using memorization or dynamic programming could bring this problem down to O(n^2).

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class WordSegment {

Map<String, String> memoized = new HashMap<String, String>();

public String SegmentString(String input, Set<String> dict) {
if (dict.contains(input))
return input;
if (memoized.containsKey(input)) {
return memoized.get(input);
int len = input.length();
for (int i = 1; i < len; i++) {
String prefix = input.substring(0, i);
if (dict.contains(prefix)) {
String suffix = input.substring(i, len);
String segSuffix = SegmentString(suffix, dict);
if (segSuffix != null) {
memoized.put(input, prefix + " " + segSuffix);
return prefix + " " + segSuffix;


memoized.put(input, null);
return null;

No comments: