寻找双打子集的有效算法和子集在一起
Efficient algorithm for finding subset with doubles and subset is together
我有两个带有字母的数组。
我想知道数组 A 是否包含在数组 B 中,如下所示:
A 中的字母必须在数组 B 中彼此相邻出现,但不必以与数组 A 中相同的顺序出现。
将被接受的例子
A = abcd
B = hbadcg
A = aabc
B = abcag
不被接受的例子
A = aabcd
B = adcbga
A = abcd
B = abbcdg
我能做的是对 A 的每个变体检查它是否是 B 中的子字符串。但我正在寻找更好的方法
考虑对给定的问题使用两点法。
- 将 A 中每个字符的计数存储在哈希映射中 -
HashMapA
- 在遍历数组 B 时维护两个指针,start 和 end。
- 维护另一个哈希映射以存储出现在数组 B 中 [start, end] 范围内的字符数 -
HashMapB
共享 ideone link 同样:https://ideone.com/vLmaxL
for(char c : A) HashMapA[c]++;
start = 0
for(int end = 0; end < B.length(); end++) {
char c = B[end];
HashMapB[c]++;
while(HashMapB[c] > HashMapA[c] && start <= end) {
HashMapB[ B[start] ]--;
start++;
}
if(end - start + 1 == A.length())
return true;
}
return false;
我有两个带有字母的数组。 我想知道数组 A 是否包含在数组 B 中,如下所示: A 中的字母必须在数组 B 中彼此相邻出现,但不必以与数组 A 中相同的顺序出现。 将被接受的例子
A = abcd B = hbadcg
A = aabc B = abcag
不被接受的例子
A = aabcd B = adcbga
A = abcd B = abbcdg
我能做的是对 A 的每个变体检查它是否是 B 中的子字符串。但我正在寻找更好的方法
考虑对给定的问题使用两点法。
- 将 A 中每个字符的计数存储在哈希映射中 -
HashMapA
- 在遍历数组 B 时维护两个指针,start 和 end。
- 维护另一个哈希映射以存储出现在数组 B 中 [start, end] 范围内的字符数 -
HashMapB
共享 ideone link 同样:https://ideone.com/vLmaxL
for(char c : A) HashMapA[c]++;
start = 0
for(int end = 0; end < B.length(); end++) {
char c = B[end];
HashMapB[c]++;
while(HashMapB[c] > HashMapA[c] && start <= end) {
HashMapB[ B[start] ]--;
start++;
}
if(end - start + 1 == A.length())
return true;
}
return false;