package Q17_13_ReSpace;_x000D_
_x000D_
import java.util.HashSet;_x000D_
_x000D_
import CtCILibrary.AssortedMethods;_x000D_
public class QuestionA {	_x000D_
	public static String bestSplit(HashSet<String> dictionary, String sentence) {_x000D_
		ParseResult r = split(dictionary, sentence, 0);_x000D_
		return r == null ? null : r.parsed;_x000D_
	}_x000D_
	_x000D_
	public static ParseResult split(HashSet<String> dictionary, String sentence, int start) {_x000D_
		if (start >= sentence.length()) {_x000D_
			return new ParseResult(0, "");_x000D_
		} _x000D_
_x000D_
		int bestInvalid = Integer.MAX_VALUE;_x000D_
		String bestParsing = null;_x000D_
_x000D_
		String partial = "";_x000D_
		int index = start;_x000D_
		while (index < sentence.length()) {_x000D_
			char c = sentence.charAt(index);_x000D_
			partial += c;_x000D_
			int invalid = dictionary.contains(partial) ? 0 : _x000D_
				partial.length();_x000D_
			if (invalid < bestInvalid) { // Short circuit_x000D_
				/* Recurse, putting a space after this character. If this_x000D_
				 * is better than the current best option, replace the best_x000D_
				 * option. */_x000D_
				ParseResult result = split(dictionary, sentence, index + 1);_x000D_
				if (invalid + result.invalid < bestInvalid) {_x000D_
					bestInvalid = invalid + result.invalid;_x000D_
					bestParsing = partial + " " + result.parsed;_x000D_
					if (bestInvalid == 0) break;_x000D_
				}_x000D_
			}_x000D_
			_x000D_
			index++;_x000D_
		}_x000D_
		return new ParseResult(bestInvalid, bestParsing);_x000D_
	}_x000D_
_x000D_
	_x000D_
	public static String clean(String str) {_x000D_
		char[] punctuation = {',', '"', '!', '.', '\'', '?', ','};_x000D_
		for (char c : punctuation) {_x000D_
			str = str.replace(c, ' ');_x000D_
		}_x000D_
		return str.replace(" ", "").toLowerCase();_x000D_
	}_x000D_
	_x000D_
	public static void main(String[] args) {_x000D_
		HashSet<String> dictionary = AssortedMethods.getWordListAsHashSet();_x000D_
		String sentence = "As one of the top companies in the world, Google"; // will surely attract the attention of computer gurus. This does not, however, mean the company is for everyone.";_x000D_
		sentence = clean(sentence);_x000D_
		System.out.println(sentence);_x000D_
		//Result v = parse(0, 0, new HashMap<Integer, Result>());_x000D_
		//System.out.println(v.parsed);_x000D_
		System.out.println(bestSplit(dictionary, sentence));_x000D_
	}_x000D_
_x000D_
}_x000D_

//Result v = parse(0, 0, new HashMap<Integer, Result>());_x000D_
package Q17_13_ReSpace;_x000D_
_x000D_
import java.util.HashSet;_x000D_
_x000D_
import CtCILibrary.AssortedMethods;_x000D_
public class QuestionA {	_x000D_
	public static String bestSplit(HashSet<String> dictionary, String sentence) {_x000D_
		ParseResult r = split(dictionary, sentence, 0);_x000D_
		return r == null ? null : r.parsed;_x000D_
	}_x000D_
	_x000D_
	public static ParseResult split(HashSet<String> dictionary, String sentence, int start) {_x000D_
		if (start >= sentence.length()) {_x000D_
			return new ParseResult(0, "");_x000D_
		} _x000D_
_x000D_
		int bestInvalid = Integer.MAX_VALUE;_x000D_
		String bestParsing = null;_x000D_
_x000D_
		String partial = "";_x000D_
		int index = start;_x000D_
		while (index < sentence.length()) {_x000D_
			char c = sentence.charAt(index);_x000D_
			partial += c;_x000D_
			int invalid = dictionary.contains(partial) ? 0 : _x000D_
				partial.length();_x000D_
			if (invalid < bestInvalid) { // Short circuit_x000D_
				/* Recurse, putting a space after this character. If this_x000D_
				 * is better than the current best option, replace the best_x000D_
				 * option. */_x000D_
				ParseResult result = split(dictionary, sentence, index + 1);_x000D_
				if (invalid + result.invalid < bestInvalid) {_x000D_
					bestInvalid = invalid + result.invalid;_x000D_
					bestParsing = partial + " " + result.parsed;_x000D_
					if (bestInvalid == 0) break;_x000D_
				}_x000D_
			}_x000D_
			_x000D_
			index++;_x000D_
		}_x000D_
		return new ParseResult(bestInvalid, bestParsing);_x000D_
	}_x000D_
_x000D_
	_x000D_
	public static String clean(String str) {_x000D_
		char[] punctuation = {',', '"', '!', '.', '\'', '?', ','};_x000D_
		for (char c : punctuation) {_x000D_
			str = str.replace(c, ' ');_x000D_
		}_x000D_
		return str.replace(" ", "").toLowerCase();_x000D_
	}_x000D_
	_x000D_
	public static void main(String[] args) {_x000D_
		HashSet<String> dictionary = AssortedMethods.getWordListAsHashSet();_x000D_
		String sentence = "As one of the top companies in the world, Google"; // will surely attract the attention of computer gurus. This does not, however, mean the company is for everyone.";_x000D_
		sentence = clean(sentence);_x000D_
		System.out.println(sentence);_x000D_
		//Result v<SUF>
		//System.out.println(v.parsed);_x000D_
		System.out.println(bestSplit(dictionary, sentence));_x000D_
	}_x000D_
_x000D_
}_x000D_
