/
ExtraCharactersInAString.java
68 lines (56 loc) · 1.81 KB
/
ExtraCharactersInAString.java
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// https://leetcode.com/problems/extra-characters-in-a-string
class Solution {
public int minExtraChar(String s, String[] dictionary) {
TrieNode root = new TrieNode();
for (String word: dictionary) {
TrieNode t = root;
for (char c: word.toCharArray()) {
int level = c - 'a';
if (t.children[level] == null) {
t.children[level] = new TrieNode();
}
t = t.children[level];
}
t.isEnd = true;
t.length = word.length();
}
char[] c = s.toCharArray();
int[] memo = new int[s.length()];
Arrays.fill(memo, - 1);
return s.length() - getUsed(c, 0, root, memo);
}
int getUsed(char[] c, int start, TrieNode root, int[] memo) {
if (start >= c.length) {
return 0;
}
if (memo[start] != -1) {
return memo[start];
}
TrieNode t = root;
int max = 0;
for (int i = start; i < c.length; i++) {
int level = c[i] - 'a';
t = t.children[level];
if (t == null) {
max = Math.max(max, getUsed(c, start + 1, root, memo));
break;
}
else if (t.isEnd) {
// We can choose to include this, or not include
max = Math.max(
max,
t.length + getUsed(c, i + 1, root, memo)
);
}
}
// Check with start + 1 anyway if somehow it was missed.
max = Math.max(max, getUsed(c, start + 1, root, memo));
memo[start] = max;
return max;
}
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEnd = false;
int length;
}
}