亚麻OA面经

寻找 redundant words 的一道题。


题目：计算一个字符串中所有符合特定条件的子字符串的数量。


给定一个字符串 word，以及两个整数 a 和 b
子串“冗余”的条件是：子串

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式

求各位大神加米，我需要米看面经啊。
谢谢谢谢了！

Heath79 发表于 2024-8-9 09:07
楼主你好，感谢分享。这题看起来只能暴力解了：遍历找到元音个数，然后暴力求解是吗？我这边好像想不到更好 ...

我事后想了想，前缀加哈希的方式应该效率更高。

Heath79 发表于 2024-8-9 09:07
楼主你好，感谢分享。这题看起来只能暴力解了：遍历找到元音个数，然后暴力求解是吗？我这边好像想不到更好 ...

是的，可以等大神们出现了再给一些思路

只有一道题嘛，能不能share 下第二道，谢谢

请问是双指针substring 吗

楼主是full time嘛

楼主你好，感谢分享。这题看起来只能暴力解了：遍历找到元音个数，然后暴力求解是吗？我这边好像想不到更好的解法，希望交流。谢谢！

不知道是不是我理解错了，我理解substring长度=元音数*a+辅音数*b。如果是这样的话，ab取值只能是三种情况，a=b=1（这种情况下任意substring都成立，直接拿长度算就行）或者a<=0 and b > 1或者a>1 and b<=0，其他情况下直接返回0就行了。

南宫狗剩 发表于 2024-8-13 21:48
不知道是不是我理解错了，我理解substring长度=元音数*a+辅音数*b。如果是这样的话，ab取值只能是三种情况 ...

word = "abbacc"，a = -1，b = 2。

"abbacc" 中的冗余子字符串如下所示：

| 子字符串 | 元音 | 辅音 | 长度 | 计算结果   |
| -------- | ---- | ---- | ---- | ---------- |
| "abb"    | 1    | 2    | 3    | -1*1 + 2*2 = 3 |
| "bba"    | 1    | 2    | 3    | -1*1 + 2*2 = 3 |
| "abbacc" | 2    | 4    | 6    | -1*2 + 2*4 = 6 |

你参考一下这个例子。就是子串长度和后面计算出来的一样。

Heath79 发表于 2024-8-9 19:07
楼主你好，感谢分享。这题看起来只能暴力解了：遍历找到元音个数，然后暴力求解是吗？我这边好像想不到更好 ...

dp一下算不算暴力啊，，或许，用dp[i][j]存substring(i,j)的元音数*a+辅音数*b, O(n^2)遍历判断