0%

leetcode每日一题-恢复空格

Posted on In ,

恢复空格

image1

方法一：暴力算法

暴力算法也就是动态规划，我们记$dp[i]$为前$i$个字符中未识别的字符数。那么就会有两种情况：

  1. 第$i$个字符与前面的字符不能组成dictionary中的单词：

$$
dp[i] = dp[i-1]+1
$$

  1. 前面第$j(j<=i)$个字符到第$i$个字符组成的子串能在dictionary中找到：

$$
dp[i] = min(dp[i],dp[j-1])
$$

1
class Solution {
2
    public int respace(String[] dictionary, String sentence) {
3
        Set<String> set = new HashSet<>();
4
        for(String s : dictionary){
5
            set.add(s);
6
        }
7
        int n = sentence.length();
8
        int[] dp = new int[n+1];
9
        dp[0] = 0;
10
        for(int i=1; i<=n; i++){
11
            dp[i] = dp[i-1] + 1;
12
            for(int j=0; j<i; j++){
13
              	//判断子串是否在dictionary中
14
                if(set.contains(sentence.substring(j,i))){
15
                    dp[i] = Math.min(dp[i], dp[j]);
16
                }
17
            }
18
        }
19
        return dp[n];
20
    }
21
}

复杂度分析：

  • 时间复杂度：$O(n^2+|dictionary|)$，其中$|dictionary|$代表词典中的总字符数。
  • 空间复杂度：$O(|dictionary|*S + n)$，其中$S$代表字符集大小，这里为小写字母数，因此$S=26$。$dp$数组的空间代价为$O(n)$。

方法二：优化方法一

上述代码套了两层循环，缺点就是对于每一个i，它前面的子字符串都被找了个遍，这其中包括一些根本不可能在字典中出现的单词。需要找一个方法提前结束。
一种方法是记录字典中每个单词最后一个字符，如果想匹配的字符串的最后一个字母都不在字典里，就没必要再看这个字符串了；此外，即使字符串最后一个字母在词典里，也不用挨个去找[j,i)子字符串是否匹配，即不需要让j从0到i遍历一遍，只要看对应长度的子串在不在词典里即可。

1
class Solution {
2
    public int respace(String[] dictionary, String sentence){
3
        Set<String> set = new HashSet<>();
4
        Map<Character, Set<Integer>> map = new HashMap<>();
5
        for(String s : dictionary){
6
            set.add(s);
7
            int len = s.length();
8
            char c = s.charAt(len-1);
9
            Set<Integer> value = map.getOrDefault(c, new HashSet<>());
10
            value.add(len);
11
            map.put(c, value);
12
        }
13
        int n = sentence.length();
14
        int[] dp = new int[n+1];
15
        for(int i=1; i<=n; i++){
16
            dp[i] = dp[i-1]+1;
17
            char c = sentence.charAt(i-1);
18
            if(map.containsKey(c)){
19
                Set<Integer> lens = map.get(c);
20
                Iterator<Integer> it = lens.iterator();
21
                while(it.hasNext()){
22
                    int len = it.next();
23
                    if(i-len>=0 && set.contains(sentence.substring(i-len, i)))
24
                    {
25
                        dp[i] = Math.min(dp[i], dp[i-len]);
26
                    }
27
                }
28
            }
29
        }
30
        return dp[n];
31
    }
32
}

复杂度分析：

  • 时间复杂度：$O(n^2+|dictionary|)$
  • 空间复杂度：$O(|dictionary|*S + n)$

方法三：字典树

在查找子串$sentence[j…i-1]$的过程中，还可以用字典树来进行优化查询。

1
class Trie{
2
    public Trie[] next;
3
    public boolean isEnd;
4
    public Trie(){
5
        next = new Trie[26];
6
        isEnd = false;
7
    }
8
    public void insert(String s){
9
        Trie curPos = this;
10
        for(int i=s.length()-1; i>=0; i--){
11
            int t = s.charAt(i) - 'a';
12
            if(curPos.next[t] == null){
13
                curPos.next[t] = new Trie();
14
            }
15
            curPos = curPos.next[t];
16
        }
17
        curPos.isEnd = true;
18
    }
19
}
20
21
class Solution {
22
    public int respace(String[] dictionary, String sentence){
23
        Trie root = new Trie();
24
        for(String s : dictionary){
25
            root.insert(s);
26
        }
27
        int n = sentence.length();
28
        int[] dp = new int[n+1];
29
        dp[0] = 0;
30
        for(int i=1; i<=n; i++){
31
            dp[i] = dp[i-1] + 1;
32
            Trie node = root;
33
            for(int j=i; j>=1; j--){
34
                int t = sentence.charAt(j-1) - 'a';
35
                if(node.next[t] == null){
36
                    break;
37
                }else if(node.next[t].isEnd){
38
                    dp[i] = Math.min(dp[i], dp[j-1]);
39
                }
40
                if(dp[i] == 0){
41
                    break;
42
                }
43
                node = node.next[t];
44
            }
45
        }
46
        return dp[n];
47
    }
48
}

复杂度分析：

  • 时间复杂度：$O(n^2+|dictionary|)$
  • 空间复杂度：$O(|dictionary|*S + n)$