恢复空格

你的益达

发布于 2020-08-05 14:42:29

7.3K0

问题描述：

哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子”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) <= 1000
dictionary中总字符数不超过 150000。
你可以认为dictionary和sentence中只包含小写字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/re-space-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

大体思路：

首先定义长度为N + 1的一维整型数组记做dp,dp[i] 表示以i开头最少未识别字符的数量。其中N为字符串sentence的长度。

其转移方程如下：

dp[i] = \begin{cases}dp[i + 1] + 1 \qquad\qquad \qquad \qquad \quad \forall arr[i:j]\notin dictionary\\\min(dp[i + 1] + 1, dp[j + 1]) \qquad \exists arr[i:j]\in dictionary\end{cases}

baseline:

dp[N] =0

大体思路确定了，现在的问题是如何实现dictionary，一种常规的做法是使用哈希表存储，但是考虑到其存在大量的重复计算并未采用哈希表而是使用前缀树存储。举例说明哈希表的重复计算，案例如下：

dictionary = ["a","ab","apple","orange"]
sentence = "banana"

不妨以i=0的情况，对于使用哈希表存储的情况，他会依次判断“b”，“ba”，“baba”,”banan”,”banana”，使用前缀树存储的情况，发现以“b”开头的就不存在与字典中，就不会进行后续操作了。

代码如下：

class Solution {
    public static class Node{
        Node[] next;
        boolean isEnd;
        public Node(){
            this.next = new Node[26];
            this.isEnd = false;
        }
    }
    public static class Tri{
        Node root;
        public Tri(){
            root = new Node();
        }
        public void insert(String s){
            Node cur = root;
            for(int i = 0; i < s.length(); i++){
                char c = s.charAt(i);
                if(cur.next[c - 'a'] == null){
                    cur.next[c - 'a'] = new Node();
                }
                cur = cur.next[c - 'a'];
            }
            cur.isEnd = true;
        }
        // 返回以i开始的最少未识别的字符数量
        public int getMin(int i, char[] arr, int[] dp){
            Node cur = root;
            int ans = dp[i + 1] + 1;
            for(;i < arr.length; i++){
                if(cur.next[arr[i] - 'a'] == null){

                    break;
                }
                cur = cur.next[arr[i] - 'a'];
                if(cur.isEnd){
                    ans = Math.min(ans, dp[i + 1]);
                }
            }
            return ans;

        }
    }
    public int respace(String[] dictionary, String sentence) {
        Tri tri = new Tri();
        for(String s : dictionary){
            tri.insert(s);
        }
        char[] arr = sentence.toCharArray();
        int N = arr.length;
        // dp[i] 为以i开头的最少未识别字符数量
        int[] dp = new int[N + 1];
        for(int i = N - 1; i >= 0; i--){
            dp[i] = tri.getMin(i, arr, dp);
        }
        return dp[0];
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-07-09，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法