[CareerCup] 17.14 Unconcatenate Words 断词 - Grandyang - 博客园
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.
我们需要拆分字符串，LeetCode中有类似的题目Word Break II和Word Break，但是又有不同，这道题允许有无法拆分的单词，那么对于这种问题，我们的目的是使无效的字母越少越好，基本的解法见parseSimple()函数，该函数可以有两点优化：
1. 一些递归重复计算了，我们可以使用哈希表来保存之前计算好的最优拆分了，那么在之后的递归中遇到了直接取出来用就行了。
2. 在有些情况下我们可以预测一种拆分方式是否会生成无效单词，比如当我们拆分单词xten，没有单词是以xt开头的，但是当前的算法会计算xt+p(en)，xten+p(n)和xten。每一次我们都会发现这样的单词不存在，这样我们直接在x后面加一个空格就可以了，那么我们怎么样知道没有单词是以xt开始的呢，用前缀树trie，参见parseOptimized()函数。
我们使用哈希表来缓存结果，关键字是单词的起始位置，我们保存了最佳的位置来拆分余下的字符串。我们可以让代码返回拆分好的字符串，但是比较麻烦。我们使用一个外包类Result来返回无效字符的个数和最优字符串，而在C++中就不用这样，因为可以通过引用传递。
Read full article from [CareerCup] 17.14 Unconcatenate Words 断词 - Grandyang - 博客园
No comments:
Post a Comment