leetcode面试题 17.13. 恢复空格

leetcode面试题 17.13. 恢复空格

八月 13, 2020

面试题 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中只包含小写字母。

动态规划

首先先处理字典，我选择了用hashmap，首字母对应字符串的形式，还有用字典树的，不过字典树写起来有一些复杂。
动态规划的思路：一个一维dp数组，dp[i]表示以i结尾能匹配的最大字符数量。
对于每一个字母，都去字典里面查找有没有合适的单词。

  • 如果找到了一个单词，就让（i+单词长度）位置的dp为当前能匹配的最大字符数量，也就是 dp[i+length-1] = max(dp[i-1]+length,dp[i+length-1]) .其中dp[i-1]用来表示已经匹配的最大长度。注意是最大长度，所以要取max。
  • 如果没有对应的单词，就让 dp[i] = max(dp[i-1],dp[i]) 。这里也要取最大值。
    下面是填表的过程，上面这些公式都是填表时候一起出来的，而不是先想出来公式，再去填表，做了几道看似困难的dp，我都是这么做出来的，所以建议自己画个表试试看。
    在这里插入图片描述
    下面是代码,show的位置可以很清晰的看出数组的变化情况。
    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
    class Solution {
        public int respace(String[] dictionary, String sentence) {
            if (sentence.length() == 0) return 0;
            int[] dp = new int[sentence.length()];
            //处理字典
            HashMap<Character,ArrayList<String>> map = new HashMap<>(1024);
            for (String s : dictionary) {
                ArrayList<String> list = map.getOrDefault(s.charAt(0),new ArrayList());
                list.add(s);
                map.put(s.charAt(0),list);
            }
            //处理结束，开始执行算法
            for (int i = 0; i < sentence.length(); i++) {
                char c = sentence.charAt(i);
                ArrayList<String> list = map.get(c);
                if (list != null) {
                //对于这个首字母的每一个单词都比较
                    for (String s : list) {
                        if (i + s.length() <= sentence.length()) {
                            String t = sentence.substring(i,i + s.length());
                            if (t.equals(s)) {
                                int n = i + s.length() - 1;
                                if (i >= 1) {
                                    dp[n] = Math.max(dp[i - 1] + s.length(), dp[n]);
                                } else {
                                    dp[n] = s.length();
                                }
                                //show(dp);
                            }
                        }
                    }
                }
                if (i > 0)
                dp[i] = Math.max(dp[i - 1],dp[i]);
                
            }
            //show(dp);
            //最后一个位置的值表示能匹配的最多的字母数量，所以减一下就行
            return sentence.length() - dp[dp.length - 1];
        }
        public void show(int[] arr) {
            for (int i : arr) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
    leetcode 117