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;
	}
}