LeetCode 程序员面试金典面试题 17.13 恢复空格

Ciel Yang 收录于类别练习 OJ解题报告

2020-07-09 2020-07-09 约 1299 字预计阅读 3 分钟

本题是一道需要慢慢分析的经典例题，需要从最初的暴力思路开始不断优化程序结构，并非是一道机械的模板题目，值得反复研究。

题目描述

原题链接如下： LeetCode 程序员面试金典面试题 17.13 恢复空格

题目大意

本题无需考虑大小写问题，只需要从句子中不断剔除字典中有的单词，然后使得剩余的字符数量最小。

输入与输出

示例输入为：

1
2
dictionary = ["looked","just","like","her","brother"]
sentence = "jesslookedjustliketimherbrother"

上述输入断句后为 “jess looked just like tim her brother”，其中 jess 和 tim 不在字典中，所以对应输出为：

1
7

解题思路

本题地最终方案需要不断地优化，而且除去动态规划方法外还有其他解法，思路基本一致，但是实际的运行效率没有明显胜过下述方法故不再赘述。

递归分解

可以把原句 s 分为任意 2 个部分，如下所示：

1
s = a + b

那么，假设未对应的字符数量关于字符串的函数为 F(s)，那么显然有：

$$F(s) \ge F(a) + F(b)$$

所以，我们从左到右分割 s，能够得到一系列的 $a_i$ 和 $b_i$ 的和，那么就有：

$$F(s) = \min {\lbrace F(a_i) + F(b_i) \rbrace}$$

这样，我们就递归地把原问题划分为了同类型地子问题。但是，这样虽然可以使用记忆化搜索解决问题，但是两个子问题的求解过程仍显繁琐，还可以考虑如何继续优化解题思路。

优化子问题结构

一般来说，我们在遇到两个并列的同类型子问题的时候，可以思考能否缩小一个子问题的涵盖范围，将它特殊化以方便快速求值。当然，另一个子问题的涵盖范围也要相应扩大以“接收”特殊化处理后被“抛弃”的一些情况。本题中我们不妨把子串 a 特殊化，认为它只包含一个单词，那么：

$$ F(s) = \left\lbrace \begin{aligned} & F(b) & \text{a in dictionary} \\ & F(b) + a.length & \text{a not in dictionary} \end{aligned} \right. $$

$len(a)$ 表示求 a 的长度。

这样的划分不会影响我们求出最后的答案，而且还得到了一个更简单的子问题划分方法，也方便引入动态规划方法。我们可以设 $dp(i)$ 为字符串的下标 i 开始到结尾的子串对应的未识别字符数量，那么递推公式如下：

$$ \begin{array}{l} dp(i, j) = \left\lbrace \begin{aligned} & dp(j + 1) & \text{s[i..j] in dictionary} \\ & j - i + 1 + dp(j + 1) & \text{s[i..j] not in dictionary} \end{aligned} \right.\ \\ dp(i) = \min_{i \le j < s.length} \lbrace dp(i, j)\rbrace \end{array} $$

最后，我们发现我们把原问题转化为了不断查询子串是否在字典中的问题。

优化字典查询

我们当然可以把字典数组转化为一个集合 HashSet，然后不断截取子串并且查询子串是否在集合中，但是这样有两个问题：

原句子很长时截取子串的操作会产出海量的碎片字符串，有大量的类生成显著降低运行效率
同样起点的子串有重复查询问题，即一个短子串明确不在字典中时，以它开头的子串就都不可能在字典中
字典过大时，集合的哈希碰撞可能会比较频繁

考虑到我们要对大量的相同前缀的子串进行查询操作，不妨引入字典树保存字典数据，那么每次查询到一个子串不能由字典树中的根到任意节点的路径构成时，那么就无需检查所有以它为前缀的子串了。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    fun respace(dictionary: Array<String>, sentence: String): Int {
        val trie = Trie()
        dictionary.forEach { trie.insert(it) }
        val dp = IntArray(sentence.length + 1)
        for (i in sentence.lastIndex downTo 0) {
            dp[i] = dp[i + 1] + 1
            var curr = trie.root
            for (j in i until sentence.length) {
                val k = sentence[j] - 'a'
                curr = curr.children[k] ?: break
                if (curr.isEnd) dp[i] = minOf(dp[i], dp[j + 1])
                if (dp[i] == 0) break
            }
        }
        return dp[0]
    }
}

class TrieNode(var isEnd: Boolean = false, val children: Array<TrieNode?> = Array(26) { null })

class Trie(val root: TrieNode = TrieNode()) {

    /** Inserts a word into the trie. */
    fun insert(word: String) {
        if (word.isEmpty()) return
        var curr = root
        for (c in word) {
            val t = c - 'a'
            if (curr.children[t] == null) curr.children[t] = TrieNode()
            curr = curr.children[t]!!
        }
        curr.isEnd = true
    }
}

注意：本题中的代码为了提高运行效率，Solution 必须侵入式的了解 Trie 和 TrieNode 的内部结构，并不建议在实际项目代码中这么做。

目录

LeetCode 程序员面试金典 面试题 17.13 恢复空格