java - 用双打和子集查找子集的有效算法是在一起的
问题描述
我有两个带字母的数组。我想知道数组 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链接: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;
推荐阅读
- rest - 根据 openAPI 中的查询参数指定 RESTful API 响应
- reactjs - 更改 rowGroupPanelShow 状态后的 Aggrid 刷新
- c# - 使用 LINQ 进行列表比较时,C# 性能很慢
- java - 如何使用 Spock 在 LocalDate 中模拟静态方法?
- css - 粘性在引导列中不起作用
- java - graphql-java 中的性能问题,特别是 ExecutionStrategy#completeField() 和 ExecutionStrategy#fetchField()
- php - 使用会话值自动填充电子邮件字段 - Opencart 3.0.3.3
- azure - 使用 AJAX 表单后,任何用户都无法使用 Azure SSO 登录。可能 AJAX 表单对 App Pool 造成了问题(Asp.Net 4.7.2 MVC))
- python - 如何操作熊猫数据框行/标题?如何标注一行的价格是高于还是低于前一个价格?
- windows - 无法联系 pgAdmin 4 服务器