面试题 17.13. 恢复空格

一、题目描述

  哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"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中只包含小写字母。

二、题解

一、解题思路

  动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

  分治算法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

  两者的区别：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

  本题采用动态规划的算法:

1. 首先新建一个数组dp,长度大小位n+1,用以记录记录每一位上的最小未识别字符数；
2. 对sentence进行逐位比较，dp[i+1]默认等于前一位的最小未识别字符串加一；
   • 游标i之前的字符串与dictionary词典中的词(word)进行比较是否相同(字符串截取长度与word等长)
   • 若比较后相等，则更新dp[i+1]的值，原dp[i+1]的值和相等字符串首字母所在索引的未识别字符数两者取其小
3. 返回dp[n]，即为整个字符串的最小未识别字符数

二、代码

    public int respace(String[] dictionary, String sentence) {
        if(sentence.length() == 0)return 0;
        int n = sentence.length();
        //记录每一位上的最小未识别字符数
        int[]dp = new int[n+1];
        //逐位进行比较
        for(int i=0;i<n;i++){
            //默认前一位的未识别字符数+1
            dp[i+1] = dp[i]+1;
            for(String word:dictionary){
                //索引i 前字符串的长度大于 字典字符串的长度才可进行比较
                if((i+1<word.length())) continue; 
                if(word.equals(sentence.substring(i+1-word.length(),i+1))){
                    //字符串相等则可更新未识别的字符数
                    dp[i+1] = Math.min(dp[i+1],dp[i+1-word.length()]);                    
                }
            }
        }
        return dp[n];
    }

参考：五大常用算法之二：动态规划算法