[CC150v5] 17.14 Optimal Way to Unconcatenate Doc - Shuatiblog.com
https://www.cnblogs.com/grandyang/p/5448539.html
https://www.cnblogs.com/EdwardLiu/p/4356967.html
X. DFS+cache
The solution given in the book is very hard to understand. It uses HashMap to memorize the previous result.
After long time of struggle, I finally solved it with traditional DP approach. The key idea is to consider: "whether I insert a space after this char, or not".
dp[j] + i - j which means all words between i and j are not recognized.
https://www.cnblogs.com/grandyang/p/5448539.html
17.14 Oh, no! You have just completed a lengthy document when you have an unfortunate Find/Replace mishap. You have accidentally removed all spaces, punctuation, and capitalization in the document. A sentence like "I reset the computer. It still didn't boot!" would become "iresetthecomputeritstilldidntboot". You figure that you can add back in the punctation and capitalization later, once you get the individual words properly separated. Most of the words will be in a dictionary, but some strings, like proper names, will not.
Given a dictionary (a list of words), design an algorithm to find the optimal way of "unconcatenating" a sequence of words. In this case, "optimal" is defined to be the parsing which minimizes the number of unrecognized sequences of characters.
For example, the string "jesslookedjustliketimherbrother" would be optimally parsed as "JESS looked just like TIM her brother". This parsing has seven unrecognized characters, which we have capitalized for clarity
https://www.cnblogs.com/EdwardLiu/p/4356967.html
这是CareerCup Chapter 17的第14题，我没怎么看CareerCup上的解法，但感觉这道题跟Word Break, Palindrome Partition II很像，都是有一个dictionary, 可以用一维DP来做，用一个int[] res = new int[len+1]; res[i] refers to minimized # of unrecognized chars in first i chars, res[0]=0, res[len]即为所求。
有了维护量，现在需要考虑转移方程，如下：
int unrecogNum = dict.contains(s.substring(j, i))? 0 : i-j; //看index从j到i-1的substring在不在dictionary里，如果不在，unrecogNum=j到i-1的char数
res[i] = Math.min(res[i], res[j]+unrecogNum);
res[i] = Math.min(res[i], res[j]+unrecogNum);
8 public int optway(String s, Set<String> dict) { 9 if (s==null || s.length()==0) return 0; 10 int len = s.length(); 11 if (dict.isEmpty()) return len; 12 int[] res = new int[len+1]; // res[i] refers to minimized # of unrecognized chars in first i chars 13 Arrays.fill(res, Integer.MAX_VALUE); 14 res[0] = 0; 15 for (int i=1; i<=len; i++) { 16 for (int j=0; j<i; j++) { 17 String str = s.substring(j, i); 18 int unrecogNum = dict.contains(str)? 0 : i-j; 19 res[i] = Math.min(res[i], res[j]+unrecogNum); 20 } 21 } 22 return res[len]; 23 }
X.Trie
private static String reSpace(String input, String... dict) {
Trie trie = new Trie(dict);
char[] chars = input.toCharArray();
Map<Character, Letter> letters = trie.letters;
Letter lastLetter = null;
StringBuilder sb = new StringBuilder();
int unrecognizedCharsCount = 0;
for (int i = 0; i < chars.length; i++) {
int j = 0;
while (i + j < chars.length && letters.containsKey(chars[i + j])) {
lastLetter = letters.get(chars[i + j]);
letters = lastLetter.children;
j++;
}
if (lastLetter != null && lastLetter.wordEnd) {
if (sb.length() > 0 && sb.charAt(sb.length() - 1) != ' ') {
sb.append(' ');
}
sb.append(new String(Arrays.copyOfRange(chars, i, i + j)));
sb.append(' ');
i += (j - 1);
} else {
sb.append(chars[i]);
unrecognizedCharsCount++;
}
lastLetter = null;
letters = trie.letters;
}
System.out.println("Out: " + sb);
System.out.println("Unrecognized chars count: " + unrecognizedCharsCount);
return sb.toString();
}
private static class Trie {
private Map<Character, Letter> letters = new HashMap<>();
public Trie(String... strings) {
for (String string : strings) {
Map<Character, Letter> candidates = letters;
char[] charArray = string.toCharArray();
for (int i = 0; i < charArray.length; i++) {
char c = charArray[i];
Letter l = new Letter(i == charArray.length - 1);
if (!candidates.containsKey(c)) {
candidates.put(c, l);
candidates = l.children;
} else {
candidates = candidates.get(c).children;
}
}
}
}
}
private static class Letter {
private final boolean wordEnd;
private Map<Character, Letter> children = new HashMap<>();
public Letter(boolean wordEnd) {
this.wordEnd = wordEnd;
}
}
X. DFS+cache
String bestSplit(HashSet<String> dictionary, String sentence) {
ParseResult r = split(dictionary, sentence, 0);
return r == null ? null : r.parsed;
}
ParseResult split(HashSet<String> dictionary, String sentence, int start) {
if (start >= sentence.length()) return new ParseResult(0, "");
int bestInvalid = Integer.MAX_VALUE; // const value (2^31)-1
String bestParsing = null;
String partial = "";
int index = start; // 0
while (index < sentence.length()) {
char c = sentence.charAt(index);
partial += c;
int invalid = dictionary.contains(partial) ? 0 : partial.length();
if (invalid < bestInvalid) {
ParseResult result = split(dictionary, sentence, index+1);
if (invalid + result.invalid < bestInvalid) {
bestInvalid = invalid + result.invalid;
bestParsing = partial = " " + result.parsed;
if (bestInvalid == 0) break;
}
}
++index;
}
return new ParseResult(bestIndex, bestParsing);
}
public class ParseResult {
public int invalid = Integer.MAX_VALUE;
public String parsed = " ";
public ParseResult(int inv, String p) {
invalid = inv;
parsed = p;
}
}
String split(HashSet<String> dictionary, String sentence, int start, ParseResult[] memo) {
if (start >= sentence.length()) return new ParseResult(0, "");
if (memo[start] != null) return memo[start];
int bestValid = Integer.MAX_VALUE;
String bestParsing = null;
String partial = "";
int index = start;
while (index < sentence.length()) {
char c = sentence.chatAt(index);
partial += c;
int invalid = dictionary.contains(partial) ? 0 : partial.length();
if (invalid < bestInvalid) {
ParseResult result = split(dictionary, sentence, index+1, memo);
if (invalid + result.invalid < bestInvalid) {
bestInvalid = invalid + result.invalid;
bestParsing = partial + " " + result.parsed;
if (bestInvalid == 0) break;
}
}
++index;
}
memo[start] = new ParseResult(bestInvalid, bestParsing);
return memo[start];
}
我们需要拆分字符串，LeetCode中有类似的题目Word Break II和Word Break，但是又有不同，这道题允许有无法拆分的单词，那么对于这种问题，我们的目的是使无效的字母越少越好，基本的解法见parseSimple()函数，该函数可以有两点优化：
1. 一些递归重复计算了，我们可以使用哈希表来保存之前计算好的最优拆分了，那么在之后的递归中遇到了直接取出来用就行了。
2. 在有些情况下我们可以预测一种拆分方式是否会生成无效单词，比如当我们拆分单词xten，没有单词是以xt开头的，但是当前的算法会计算xt+p(en)，xten+p(n)和xten。每一次我们都会发现这样的单词不存在，这样我们直接在x后面加一个空格就可以了，那么我们怎么样知道没有单词是以xt开始的呢，用前缀树trie，参见parseOptimized()函数。
我们使用哈希表来缓存结果，关键字是单词的起始位置，我们保存了最佳的位置来拆分余下的字符串。我们可以让代码返回拆分好的字符串，但是比较麻烦。我们使用一个外包类Result来返回无效字符的个数和最优字符串，而在C++中就不用这样，因为可以通过引用传递。
public static String sentence; public static Trie dictionary; public static Result parse(int start, int end, Hashtable<Integer, Result> cache) { if (end >= sentence.length()) { return new Result(end - start, sentence.substring(start).toUpperCase()); } if (cache.containsKey(start)) { return cache.get(start).clone(); } String curWord = sentence.substring(start, end + 1); boolean validPartial = dictionary.contains(curWord, false); boolean validExact = validPartial && dictionary.contains(curWord, true); Result bestExact = parse(end + 1, end + 1, cache); if (validExact) { bestExact.parsed = curWord + " " + bestExact.parsed; } else { bestExact.invalid += curWord.length(); bestExact.parsed = curWord.toUpperCase() + " " + bestExact.parsed; } Result bestExtend = null; if (validPartial) { bestExtend = parse(start, end + 1, cache); } Result best = Result.min(bestExact, bestExtend); cache.put(start, best.clone()); return best; } public static int parseOptimized(int start, int end, Hashtable<Integer, Integer> cache) { if (end >= sentence.length()) { return end - start; } if (cache.containsKey(start)) { return cache.get(start); } String curWord = sentence.substring(start, end + 1); boolean validPartial = dictionary.contains(curWord, false); int bestExact = parseOptimized(end + 1, end + 1, cache); if (!validPartial || !dictionary.contains(curWord, true)) { bestExact += curWord.length(); } int bestExtend = Integer.MAX_VALUE; if (validPartial) { bestExtend = parseOptimized(start, end + 1, cache); } int min = Math.min(bestExact, bestExtend); cache.put(start, min); return min; } public static int parseSimple(int start, int end) { if (end >= sentence.length()) { return end - start; } String word = sentence.substring(start, end + 1); int bestExact = parseSimple(end + 1, end + 1); if (!dictionary.contains(word, true)) { bestExact += word.length(); } int bestExtend = parseSimple(start, end + 1); return Math.min(bestExact, bestExtend); }
The solution given in the book is very hard to understand. It uses HashMap to memorize the previous result.
After long time of struggle, I finally solved it with traditional DP approach. The key idea is to consider: "whether I insert a space after this char, or not".
dp[j] + i - j which means all words between i and j are not recognized.
public static int parse(String doc, Trie dict) {
int len = doc.length();
int[] dp = new int[len + 1];
// dp[i] denotes the number of special chars in first i chars of docs
for (int i = 1; i <= len; i++) {
dp[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
String str = doc.substring(j, i);
if (dict.contains(str, true)) {
// consider (i to j) a valid word
dp[i] = Math.min(dp[i], dp[j]);
} else {
// consider (i to j) special chars
dp[i] = Math.min(dp[i], dp[j] + i - j);
}
}
}
return dp[len];
}8 public int optway(String s, Set<String> dict) { 9 if (s==null || s.length()==0) return 0; 10 int len = s.length(); 11 if (dict.isEmpty()) return len; 12 int[] res = new int[len+1]; // res[i] refers to minimized # of unrecognized chars in first i chars 13 Arrays.fill(res, Integer.MAX_VALUE); 14 res[0] = 0; 15 for (int i=1; i<=len; i++) { 16 for (int j=0; j<i; j++) { 17 String str = s.substring(j, i); 18 int unrecogNum = dict.contains(str)? 0 : i-j; 19 res[i] = Math.min(res[i], res[j]+unrecogNum); 20 } 21 } 22 return res[len]; 23 }Read full article from [CC150v5] 17.14 Optimal Way to Unconcatenate Doc - Shuatiblog.com
