本文最后更新于 2024年9月29日 下午
力扣周赛415
T3
T3数据量较小,可以使用字典树进行查找,由于可以查找前缀,将用于标记字符串结尾的EndNode删去,并将查找方法的返回值改为int类型
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| class Node{
char ch;
Node[] children = new Node[26];
Node(){}
Node(char ch){
this.ch = ch;
}
}
class TrieTree {
private Node root = new Node();
void insert(String s){
Node q = root;
for (char c : s.toCharArray()){
boolean flag = false;
for (Node child : q.children){
if (child == null){
continue;
}
if (child.ch == c){
q = child;
flag = true;
break;
}
}
if (!flag){
Node newNode = new Node(c);
q.children[c - 'a'] = newNode;
q=newNode;
}
}
}
int search(String s){
Node q = root;
int ans = 0;
for (char c : s.toCharArray()){
boolean flag = false;
for (Node child : q.children){
if (child == null){
continue;
}
if (child.ch == c){
flag = true;
q = child;
break;
}
}
if (!flag){
return ans;
}
ans++;
}
return ans;
}
}
class Solution {
public int minValidStrings(String[] words, String target) {
TrieTree trietree = new TrieTree();
int maxLen = 0;
for (String s : words){
trietree.insert(s);
maxLen = Math.max(maxLen, s.length());
}
int currRight = 0;
int nextRight = 0;
int step = 0;
for (int i = 0; i < target.length(); i++){
int left = i;
int right = Math.min(i + maxLen, target.length());
nextRight = Math.max(nextRight, left + trietree.search(target.substring(left,right)));
if (currRight == i){
if (nextRight == currRight){
return -1;
}
else{
currRight = nextRight;
}
step++;
}
}
return step;
}
}
|
附:字典树模板
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
69
70
71
72
| class Node{
char ch;
Node[] children = new Node[27];
Node(){}
Node(char ch){
this.ch = ch;
}
}
class EndNode extends Node{
EndNode(){}
}
public class TrieTree {
private Node root = new Node();
void insert(String s){
Node q = root;
for (char c : s.toCharArray()){
boolean flag = false;
for (Node child : q.children){
if (child == null){
continue;
}
if (child.ch == c){
q = child;
flag = true;
break;
}
}
if (!flag){
Node newNode = new Node(c);
q.children[c - 'a'] = newNode;
q = q.children[c - 'a'];
}
}
q.children[26] = new EndNode();
}
boolean search(String s){
Node q = root;
for (char c : s.toCharArray()){
boolean flag = false;
for (Node child : q.children){
if (child == null){
continue;
}
if (child.ch == c){
flag = true;
q = child;
break;
}
}
if (!flag){
return false;
}
}
return q.children[26] != null;
}
public static void main(String[] args){
TrieTree trieTree = new TrieTree();
trieTree.insert("abcde");
trieTree.insert("abcd");
trieTree.insert("fjklnhmasdjk");
trieTree.insert("abcdef");
System.out.println(trieTree.search("abc"));
System.out.println(trieTree.search("abcde"));
System.out.println(trieTree.search("abcdef"));
}
}
|
T4
字符串哈希
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
| class Solution {
private static final int MOD = 1_070_777_777;
public int minValidStrings(String[] words, String target) {
char[] t = target.toCharArray();
int n = t.length;
final int BASE = (int)8e8 + new Random().nextInt((int) 1e8);
int[] powBase = new int[n+1];
int[] preHash = new int[n+1];
powBase[0] = 1;
for (int i = 0; i < n; i++){
powBase[i+1] = (int)((long) powBase[i] * BASE % MOD);
preHash[i+1] = (int)(((long) preHash[i] * BASE + t[i]) % MOD);
}
int maxLen = 0;
for (String w : words){
maxLen = Math.max(maxLen, w.length());
}
Set<Integer>[] sets = new HashSet[maxLen];
Arrays.setAll(sets, i -> new HashSet<>());
for (String w : words){
long h = 0;
for (int j = 0; j < w.length(); j++){
h = (h * BASE + w.charAt(j)) % MOD;
sets[j].add((int) h);
}
}
int ans = 0;
int curRight = 0;
int nextRight = 0;
for (int i = 0; i < n; i++){
int sz = calcSz(i, preHash, powBase, sets);
nextRight = Math.max(nextRight, i+sz);
if (i == curRight){
if (i == nextRight){
return -1;
}
curRight = nextRight;
ans++;
}
}
return ans;
}
private int calcSz(int i, int[] preHash, int[] powBase, Set<Integer>[] sets){
int left = 0;
int right = Math.min(preHash.length - 1 - i, sets.length) + 1;
while (left + 1 < right){
int mid = (left + right) >>> 1;
long subHash = ( ((long) preHash[i + mid] - (long) preHash[i] * powBase[mid]) % MOD + MOD) % MOD;
if (sets[mid-1].contains((int) subHash)){
left = mid;
}
else{
right = mid;
}
}
return left;
}
}
|
AC自动机
前缀函数
计算方式
计算字符串前k位多少位前缀和与后缀和相等,如"abcabcd":[0,0,0,1,2,3,0]
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
| import java.util.Arrays;
public class PrefixCount {
public int[] prefixCount(int[] arr) {
int[] ret = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
for (int j = i / 2 + 1; j <= i; j++) {
boolean flag = true;
int k = 0, p = j;
while (p <= i) {
if (arr[k++] != arr[p++]) {
flag = false;
break;
}
}
if (flag) {
ret[i] = k;
break;
}
}
}
return ret;
}
public static void main(String[] args) {
int[] arr = {1, 1, 2, 1, 1, 1, 2};
System.out.println(Arrays.toString(
new PrefixCount().prefixCount(arr)));
}
}
|
优化
对于\(ret[k](k>1)\),它只可能比\(ret[k-1]\)多1,或者维持不变或减少,这里我们改为字符串输入,并使用subString()和equals()方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| import java.util.Arrays;
public class PrefixCount {
public int[] prefixCount(String s) {
int n = s.length();
int[] ret = new int[n];
for (int i = 1; i < n; i++) {
for (int j = ret[i-1] + 1; j >= 0; j--) {
if (s.substring(0, j).equals(s.substring(i-j+1, i+1))) {
ret[i] = j;
break;
}
}
}
return ret;
}
public static void main(String[] args) {
String s = "abcabcd";
System.out.println(Arrays.toString(
new PrefixCount().prefixCount(s)));
}
}
|
最终算法
考虑当\(s[i+1] \neq
s[ret[i]]\)时如何跳转,令j为\(s[i+1]
\neq s[ret[i]]\)时选择的第二长度
状态转移:\(j^{(n)}=\pi[j^{(n-1)}-1]\)
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
| import java.util.Arrays;
public class PrefixCount {
public int[] prefixCount(String s) {
int n = s.length();
int[] ret = new int[n];
for (int i = 1; i < n; i++) {
int j = ret[i-1];
while (j > 0 && s.charAt(i) != s.charAt(j)) {
j = ret[j-1];
}
if (s.charAt(i) == s.charAt(j)) {
j++;
}
ret[i] = j;
}
return ret;
}
public static void main(String[] args) {
String s = "abcabcde";
System.out.println(Arrays.toString(
new PrefixCount().prefixCount(s)));
}
}
|
KMP
Knuth-Morris-Pratt算法
给定一个文本text和字符串pattern,找到pattern在text中的所有出现
构造一个字符串:pattern+"#"+text,调用计算前缀函数的方法,获得结果数组,对于\(i>pattern.length()\),若\(ret[i]==pattern.length()\),则可以判断在text中的第\(i-2\cdot
pattern.length()\)处出现pattern字符串
时间复杂度\(O(n+m)\),空间复杂度\(O(n+m)\)(n,m分别为text,pattern的长度)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| import java.util.ArrayList;
import java.util.List;
public class KMP {
public List<Integer> search(String text, String pattern) {
String p = pattern + "#" + text;
int sz1 = text.length();
int sz2 = pattern.length();
List<Integer> v = new ArrayList<>();
int[] lps = new PrefixCount().prefixCount(p);
for (int i = sz2 + 1; i <= sz1 + sz2; i++) {
if (lps[i] == sz2) {
v.add(i-2 * sz2);
}
}
return v;
}
public static void main(String[] args) {
String p = "aab";
String t = "aabaabaabbcdaab";
System.out.println(new KMP().search(t, p));
}
}
|