echo

任生命穿梭 时间的角落

0%

恢复空格

Posted on In Valine:

面试题 17.13. 恢复空格

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

注意：本题相对原题稍作改动，只需返回未识别的字符数

示例：

1
2
3
4
5
输入：
dictionary = ["looked","just","like","her","brother"]
sentence = "jesslookedjustliketimherbrother"
输出： 7
解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。

提示：

  • 0 <= len(sentence) <= 1000
  • dictionary中总字符数不超过 150000。
  • 你可以认为dictionary和sentence中只包含小写字母。

创建一个数组 dp 来记录结果，dp[i]表示句子中前 i 个字符中最少的未识别字符数。dp[0] = 0 代表空字符串时2没有未识别的字符。

对于句子中前 i 个字符，有两种情况：

  • 可能由前面的 [0, j) 字符串加上一个单词构成；dp[i] = min(dp[i], dp[j])；
  • 前 i - 1 个字符加上第 i 个字符 ,dp[i] = dp[i - 1] + 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int respace(String[] dictionary, String sentence) {
        //将单词添加到 HashSet
        Set<String> dic = new HashSet<>();
        for(String s : dictionary){
            dic.add(s);
        }

        int n = sentence.length();
        int[] dp = new int[n + 1];
        for(int i = 1; i <= n; i++){
            //默认前面没有单词
            dp[i] = dp[i - 1] + 1;
            for(int j = 0; j < i; j++){
                //构成单词
                if(dic.contains(sentence.substring(j, i))){
                    dp[i] = Math.min(dp[i], dp[j]);
                }
            }
        }

        return dp[n];
    }
}

时间复杂度O(n^3)，contains 方法时间复杂度O(1)，substring 方法时间复杂度O(n)。空间复杂度O(n)。

时间复杂度较高的地方就是如何快速判断子串是否存在于词典中，这里使用「字典树 Trie」来进行优化，Trie 时是一种最大程度利用多个字符串前缀信息的数据结构，它可以在 O(w)时间复杂度内判断一个字符串是否是一个字符串集合中某个字符串的前缀，其中 w 代表字符串的长度。

我们将所有单词「反序」插入到字典树中，然后在每次判断子串末尾是否是一个单词时，从子串末尾i 开始遍历，同时在 Trie 上从根结点开始出发，当走到sentence[j] 在 Trie 上没有相应的位置，说明 sentence[j…i - 1]不是一个单词，退出循环。对于判断字典树结点是否为叶子结点，我们在单词末尾的结点上打上一个 isEnd 的标记。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Trie{
    public Trie[] next;//next结点数组
    public boolean isEnd;//结点是否为叶子结点

    public Trie(){
        next = new Trie[26];//一个结点最多有 26 个字母
        isEnd = false;
    }
	
    //将字符串 s 倒序插入字典树
    public void insert(String s){
        Trie curPos = this;
		
        for(int i = s.length() - 1; i >= 0; i--){
            int t = s.charAt(i) - 'a';
            if(curPos.next[t] == null){
                //新建结点
                curPos.next[t] = new Trie();
            }
            //向下移动
            curPos = curPos.next[t];
        }
        //最后一个结点 isEnd 设为 true
        curPos.isEnd = true;
    }
}
class Solution {
    public int respace(String[] dictionary, String sentence) {
        int n = sentence.length();
        //生成字典树
        Trie root = new Trie();
        for(String word : dictionary){
            root.insert(word);
        }
		//初始化 dp 数组
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for(int i = 1; i <= n; i++){
            //默认子串最后没有单词
            dp[i] = dp[i - 1] + 1;
            Trie curPos = root;
            //逐个判断子串末尾的字符是否在字典树中
            for(int j = i; j >= 1; j--){
                int t = sentence.charAt(j - 1) - 'a';
                if(curPos.next[t] == null){//有一个字符不在字典树的路径中
                    break;
                }else if(curPos.next[t].isEnd){//到达字典树末尾
                    dp[i] = Math.min(dp[i], dp[j - 1]);
                }
                if(dp[i] == 0){// 0 为最小值，直接退出循环
                    break;
                }
                //继续判断子串中前一个字符
                curPos = curPos.next[t];
            } 
        }
        return dp[n];
    }
}

时间复杂度O(n^2)。空间复杂度O(n)。