面试题 17.13. 恢复空格

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int respace(String[] dictionary, String sentence) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(dictionary));

        // 定义 dp[i] 为前 i 个字符组成的字符串中最少的未识别的字符数
        int[] dp = new int[sentence.length() + 1];

        for (int i = 1; i <= sentence.length(); i++) {
            dp[i] = dp[i - 1] + 1; // 最坏的情况，当前字符无法与之前的字符组成单词，此时只能增加一个未识别的字符数
            for (int j = 0; j < i; j++) {
                // 注意此处切分点的选择，不能选用 [0, j] [j + 1, i - 1] 因为这样的话右侧单词无法使用整个字符串
                // split: [0, j - 1] [j, i - 1]
                if (wordSet.contains(sentence.substring(j, i))) {
                    dp[i] = Math.min(dp[i], dp[j]);
                }
            }
        }

        return dp[sentence.length()];
    }
}

References

面试题 17.13. 恢复空格