class Solution {
public:
int respace(vector<string>& dictionary, string sentence) {
}
};
面试题 17.13. 恢复空格
哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。
注意：本题相对原题稍作改动，只需返回未识别的字符数
示例：
输入： dictionary = ["looked","just","like","her","brother"] sentence = "jesslookedjustliketimherbrother" 输出： 7 解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。
提示：
0 <= len(sentence) <= 1000dictionary中总字符数不超过 150000。dictionary和sentence中只包含小写字母。原站题解
python3 解法, 执行用时: 584 ms, 内存消耗: 15.3 MB, 提交时间: 2022-11-29 16:37:24
class Solution:
def respace(self, dictionary: List[str], sentence: str) -> int:
"""
动态规划
状态定义：f[i]，0 <= i <= len(sentence)
集合：前 i 个字符所有可能的划分方式
属性：Min(未识别的字符数)
状态转移：
集合划分：
第 i 个字符无法与前面任何一个子串组成单词：f[i - 1] + 1
第 i 个字符可以与前面某个子串组成单词：f[j]
if sentence[j:i] in dictionary，0 <= j <= i - 1
初始化：f[0] = 0，当 sentence 为空字符串时，未识别字符数为 0
答案：f[-1]
"""
d = {}.fromkeys(dictionary)
n = len(sentence)
f = [0] * (n + 1)
for i in range(1, n + 1):
f[i] = f[i - 1] + 1
for j in range(i):
if sentence[j:i] in d:
f[i] = min(f[i], f[j])
return f[-1]
golang 解法, 执行用时: 40 ms, 内存消耗: 4.6 MB, 提交时间: 2022-11-29 16:33:29
const (
P = math.MaxInt32
BASE = 41
)
func respace(dictionary []string, sentence string) int {
hashValues := map[int]bool{}
for _, word := range dictionary {
hashValues[getHash(word)] = true
}
f := make([]int, len(sentence) + 1)
for i := 1; i < len(f); i++ {
f[i] = len(sentence)
}
for i := 1; i <= len(sentence); i++ {
f[i] = f[i-1] + 1
hashValue := 0
for j := i; j >= 1; j-- {
t := int(sentence[j-1] - 'a') + 1
hashValue = (hashValue * BASE + t) % P
if hashValues[hashValue] {
f[i] = min(f[i], f[j-1])
}
}
}
return f[len(sentence)]
}
func getHash(s string) int {
hashValue := 0
for i := len(s) - 1; i >= 0; i-- {
hashValue = (hashValue * BASE + int(s[i] - 'a') + 1) % P
}
return hashValue
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
golang 解法, 执行用时: 56 ms, 内存消耗: 46.3 MB, 提交时间: 2022-11-29 16:33:03
func respace(dictionary []string, sentence string) int {
n, inf := len(sentence), 0x3f3f3f3f
root := &Trie{next: [26]*Trie{}}
for _, word := range dictionary {
root.insert(word)
}
dp := make([]int, n + 1)
for i := 1; i < len(dp); i++ {
dp[i] = inf
}
for i := 1; i <= n; i++ {
dp[i] = dp[i-1] + 1
curPos := root
for j := i; j >= 1; j-- {
t := int(sentence[j-1] - 'a')
if curPos.next[t] == nil {
break
} else if curPos.next[t].isEnd {
dp[i] = min(dp[i], dp[j-1])
}
if dp[i] == 0 {
break
}
curPos = curPos.next[t]
}
}
return dp[n]
}
type Trie struct {
next [26]*Trie
isEnd bool
}
func (this *Trie) insert(s string) {
curPos := this
for i := len(s) - 1; i >= 0; i-- {
t := int(s[i] - 'a')
if curPos.next[t] == nil {
curPos.next[t] = &Trie{next: [26]*Trie{}}
}
curPos = curPos.next[t]
}
curPos.isEnd = true
}
func min(x, y int) int {
if x < y {
return x
}
return y
}