思路
第一点的做题的总体方向，起初想到的是搜索，实际上可以用dp。
当想到用（记忆化）搜索时，就要想想能否使用dp。尤其是字符串的题目。
想到用dp后，首先要构建dp数组。这题dp数组的含义是：前i个字符的子字符串中需要连接的最小字符串数量。这样求出dp[n]即可。
字符串的最优子结构，通常可以考虑前i个字符的子串。
然后是状态转移方程，我们知道了dp[i]，如果接下来到j为止的若干个字符可以构成某个前缀，则dp[j] = min(dp[j], dp[i] + 1)。
dp中不一定是用dp[i]推出dp[i + 1]，其下标的变化可以很广泛。反之同理。
为什么我们不需要考虑当前字符要连接前面字符形成一个更长前缀的情况呢？因为如果当前字符可以连接，那么这个位置的dp值一定在之前就已经求出来，无需更新；反之，则用我们的算法就可以更新这个值。
这里的思想是我没有想到的，非常重要的一个思想。印象中在很多字符串的问题都适用。dp只向前看。
接下来我们要解决的问题就剩下如何快速判断一个字符串是不是已知字符串集合中的某个前缀了。正好，这个需求和我们之前学过的前缀树完全一致。
使用前缀树时有个小细节，由于前缀树查询有O(n)的时间复杂度，我们尽量不多次查询前缀树，因此我们可以通过前缀树找出能匹配的最长前缀长度，这样就只需要一次O(n)的查询，有了这个小优化才能通过。这样也省去了构建String的复杂度。
将逐步构建String改为求出匹配的最长前缀。
Java语言知识点
Java数组快速赋值：
1
2
| Arrays.fill(a, 0);
Arrays.setAll(a, i -> i);
|
代码
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
| class Solution {
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public int search(String prefix, int start) {
Trie node = this;
for (int i = start; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
return i - start;
}
node = node.children[index];
}
return prefix.length() - start;
}}
public int minValidStrings(String[] words, String target) {
char[] cs = target.toCharArray();
int n = cs.length;
int dp[] = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
Trie t = new Trie();
for (String s : words) {
t.insert(s);
}
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int len = t.search(target, i - 1);
if (len == 0 && dp[i] == Integer.MAX_VALUE) return -1;
for(int j = i; j < i + len; j++) {
dp[j] = Math.min(dp[j], dp[i - 1] + 1);
}
}
return dp[n];
}
}
|
