面试题 17.13. 恢复空格

每天一道Rust-LeetCode(2020-07-09)

坚持每天一道题,刷题学习Rust.

题目描述

哦,不!你不小心把一个长篇文章中的空格、标点都删掉了,并且大写也弄成了小写。像句子"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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

首先将dict转为map,加速查找.
使用动态规划思路:
i,j都是sentence中的下标
首先dp[i][j]表示从i到j(包含j)中未识别的字符数,显然这个数最大就是j-i+1
第一步,扫描整个字符串,找出所有包含在字典中的dp[i][j],然后设置为0
第二步,由短变长遍历整个dp,最终得出结果
空间复杂度是O(N^2),其中N是句子的长度
时间复杂度是O(N^3),其中N是句子的长度

解题过程


struct Solution {}
impl Solution {
    pub fn respace(dictionary: Vec<String>, sentence: String) -> i32 {
        if sentence.is_empty() {
            return 0;
        }
        let mut set = std::collections::HashSet::new();

        for s in dictionary.iter() {
            set.insert(s.as_str());
        }
        let s = sentence.as_str();
        let mut dp = vec![vec![0; sentence.len() + 1]; sentence.len() + 1];
        //第一步,扫描整个字符串,找出所有包含在字典中的dp[i][j],然后设置为0
        for i in 0..sentence.len() {
            for j in i..sentence.len() {
                if set.contains(&s[i..=j]) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = j - i + 1;
                }
            }
        }
        // println!("dp={:?}", dp);
        //第二步,由短变长遍历整个dp,最终得出结果
        for step in 1..sentence.len() {
            for i in 0..sentence.len() - step {
                //从i开始往后走step步恰好是一个单词
                let total = &s[i..=(i + step)];
                if dp[i][i + step] == 0 {
                    continue;
                }
                // if total == "jesslooked" {
                //     println!("total={}", total);
                // }
                //没有组成一个单词,就开始切分,找出切分组合中最小的情况
                let mut expected = dp[i][i + step];
                for j in 0..step {
                    if dp[i][i + j] + dp[i + j + 1][i + step] < expected {
                        expected = dp[i][i + j] + dp[i + j + 1][i + step]
                    }
                }
                dp[i][i + step] = expected;
                // println!("total={},dp[{}][{}]={}", total, i, step, dp[i][step]);
            }
        }
        dp[0][sentence.len() - 1] as i32
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::share::vec_str_to_string;
    #[test]
    fn it_works() {
        let a = Solution::respace(
            vec_str_to_string(vec!["looked", "just", "like", "her", "brother"]),
            "lookedjust".to_string(),
        );
        assert_eq!(a, 0);

        let a = Solution::respace(
            vec_str_to_string(vec!["looked", "just", "like", "her", "brother"]),
            "jesslooked".to_string(),
        );
        assert_eq!(a, 4);

        let a = Solution::respace(
            vec_str_to_string(vec!["looked", "just", "like", "her", "brother"]),
            "jesslookedjustliketimherbrother".to_string(),
        );
        assert_eq!(a, 7);

        let a = Solution::respace(
            vec_str_to_string(vec!["looked", "just", "like", "her", "brother"]),
            "".to_string(),
        );
        assert_eq!(a, 0);

        let a = Solution::respace(
            vec_str_to_string(vec!["a", "just", "like", "her", "brother"]),
            "a".to_string(),
        );
        assert_eq!(a, 0);
        return;
    }
}

一点感悟

看了别人的答案,好像复杂度比我这个好得多,后续会再来一篇优化的方案

其他

欢迎关注我的github,本项目文章所有代码都可以找到.

本站总访问量 本站访客数人次