恢复空格

发表于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

LeetCode每日一题，面试题17.13. Re-Space LCCI

先看题目描述

大意就是给定 sentence 和 dictionary，依赖 dictionary 来识别单词，让我们返回 sentence 中未识别的字符数

算法和思路

第一反应就是动态规划

  • 初始化 dp[0] = 0，dp[i + 1] 表示子串 sentence[0: i] 中未识别的字符个数
  • 状态转移方程：若 dictionary 中存在子串 sectence[j: i]，dp[i + 1] = min(dp[i + 1], dp[j])，否则 dp[i + 1] = dp[i] + 1

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.Arrays;
import java.util.List;

class Solution {
    public int respace(String[] dictionary, String sentence) {
        int[] dp = new int[sentence.length() + 1];
        List<String> dict = Arrays.asList(dictionary);
        for (int i = 0; i < sentence.length(); i++) {
            dp[i + 1] = dp[i] + 1;
            for (int j = 0; j <= i; j++) {
                if (dict.contains(sentence.substring(j, i + 1))) {
                    dp[i + 1] = Math.min(dp[i + 1], dp[j]);
                }
            }
        }
        return dp[sentence.length()];
    }
}

然后提交上去就超时了，而且不知道怎么改善运行时间，毫无头绪。后来看了题解才知道可以使用字典树 Trie 来优化查找，Trie 是一种最大程度利用多个字符串前缀信息的数据结构，它可以在 O(w) 的时间复杂度内判断一个字符串是否是一个字符串集合中某个字符串的前缀，其中 w 代表字符串的长度

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
import java.util.*;

class Solution {
    public int respace(String[] dictionary, String sentence) {
        int n = sentence.length();

        Trie root = new Trie();
        for (String word: dictionary) {
            root.insert(word);
        }

        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) {
                    break;
                }
                curPos = curPos.next[t];
            }
        }
        return dp[n];
    }
}

class Trie {
    public Trie[] next;
    public boolean isEnd;

    public Trie() {
        next = new Trie[26];
        isEnd = false;
    }

    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];
        }
        curPos.isEnd = true;
    }
}

感觉解这道题的关键就在于如何快速判断当前子串是否存在于字典中，而使用字典树 Trie 就可以优化查找，需要掌握字典树 Trie 这种数据结构