给定长度为 m 的字符串 aim,以及一个长度为 n 的字符串 str 问能否在 str 中找到一个长度为 m 的连续子串,使得这个子串刚好由 aim 的 m 个字符组成,顺序无所谓返回任意满足条件的一个子串的起始位置,未找到返回-1。

思路:

找到一个串和aim排序对比

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
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while (input.hasNext()) {
String aim = input.next();
String str = input.next();
int m = aim.length();
int i = 0;
int j = m - 1;
char[] charAim = aim.toCharArray();
Arrays.sort(charAim);
int flag = 0;
while (j != m) {
char[] sub = str.substring(i, j + 1).toCharArray();
Arrays.sort(sub);
flag = 0;
for (int k = 0; k < sub.length; k++) {
if (sub[k] != charAim[k]) {
flag = 1;
break;
}
}
if (flag == 1) {
i++;
j++;
continue;
} else {
System.out.println("true");
break;
}
}
if (flag == 1) System.out.println("false");
}
}

面试上写这个暴力算法没有分 O(n^3*logN)

优化O(N*M):

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
public boolean isTY(char[] str, int L, char[] aim) {
// 0-255 统计数组
// 'a' 97
// count[97] ++;
int[] count = new int[256];
for (int i = 0; i < aim.length; i++) {
count[aim[i]]++;
}
//count 中含有0-255
for (int i = 0; i < str.length; i++) {
if (count[str[i]] == 0) {
return false;
}
count[str[i]]--;
}
return true;
}

public int containExactly2(String a, String b) {
if (a == null || b == null || a.length() < b.length()) {
return -1;
}
char[] str = a.toCharArray();
char[] aim = b.toCharArray();
for (int L = 0; L <= str.length - aim.length; L++) {
if (isTY(str, L, aim)) {
return L;
}
}
return -1;
}

一共有N-M个要判断匹配的串,要遍历M个长度

最后优化:O(n)

先把目标字符串做成一个字典表。

出现了的字符做成一个计数字典

没有出现的就认为是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
32
33
34
35
36
37
38
39
40
41
public int containExactly(String a, String b) {
if (a == null || b == null || a.length() < b.length()) {
return -1;
}
char[] str = a.toCharArray();
char[] aim = b.toCharArray();
int[] count = new int[256];
for (int i = 0; i < aim.length; i++) {
count[aim[i]]++;
}
int M = aim.length;
int inValidTimes = 0;
int R = 0;
// 先让窗口用于M个字符
for (; R < M; R++) {
if (count[str[R]]-- <= 0) {
inValidTimes++;
}
}
// 如果第一个是同源异构词
if (inValidTimes == 0) {
return R - M;
}
// 窗口滑动
for (; R < str.length; R++) {
if (inValidTimes == 0) {
return R - M;
}
// 0[0..M-1]M
// [1..M]
// [2...M+1]
if (count[str[R]]-- <= 0) {
inValidTimes++;
}
if (count[str[R - M]]++ < 0) {
inValidTimes--;
}
}
return inValidTimes == 0 ? R - M : -1;
}