给定一个字符串,找到元音和辅音数量相同的最长子串。
澄清:我不确定我们是否可以生成一个新字符串,或者子字符串必须是原始字符串的一部分?到目前为止我有这个,
代码片段:
Scanner scanner = new Scanner(System.in);
String string = new String(scanner.next());
int lengthOfString = string.length();
int vowelCount = 0;
int consCount = 0;
for (int i = 0; i < lengthOfString; i++) {
if (string.charAt(i) == 'u' || string.charAt(i) == 'e' || string.charAt(i) == 'i'
|| string.charAt(i) == 'o' || string.charAt(i) == 'a' ) {
vowelCount++;
} else {
consCount++;
}
}
System.out.println(vowelCount);
EDIT我的计数工作正常,但如何创建子字符串?
这可以解决O(n) 时间和空间使用由以下方法计算的“净”值这个答案 https://stackoverflow.com/a/39607701/47984结合以下观察:
- 子串 s[i .. j] 具有相同数量的辅音和元音当且仅当 net[1 .. i-1] = net[1 .. j],其中 net[i .. j] 是总和位置 i 和 j(含)之间每个字符的“净”值(元音为 1,辅音为 -1)。
要看到这一点,请观察告诉我们子字符串 s[i .. j] 是我们正在寻找的类型的条件是:
net[i .. j] = 0.
将 net[1 .. i-1] 添加到该方程的两边得到
net[1 .. i-1] + net[i .. j] = net[1 .. i-1]
与 LHS 然后简化为
net[1 .. j] = net[1 .. i-1]
算法
这意味着我们可以为计算净值的运行总和时获得的每个可能的不同值创建一个包含两个条目(看到的第一个位置和看到的最后一个位置)的表。这个运行总数的范围可以低至 -n (如果每个字符都是辅音)或高至 n (如果每个字符都是元音),因此总共最多有 2n+1 个不同的此类总和,所以我们我们的表中需要那么多行。然后,我们从左到右遍历字符串,计算运行总计净值,并更新表中与当前运行总计相对应的对,并注意此更新何时产生新的最大长度子字符串。在伪代码中,使用从零开始的数组索引并使用单独的数组来保存每对中的元素:
- 创建 2 个长度为 2n+1 的数组,first[] 和 last[],最初包含所有 -2,除了 first[n] 为 -1。 (需要使用 -2 作为哨兵,因为 -1 实际上是一个有效值!)
- 设置 bestFirst = bestLast = bestLen = -1。
- 设置运行总计 t = n。 (n“意味着”0;使用此偏差仅意味着我们可以直接使用运行总计作为数组的非负值索引,而无需重复向其添加偏移量。)
- For i from 0 to n-1:
- 如果 s[i] 是元音,则递增 t,否则递减 t。
- If first[t] is -2:
- Otherwise:
- 设置最后[t] = i。
- If last[t] - first[t] > bestLen:
- 设置 bestLen = 最后[t] - 第一个[t]。
- 设置 bestFirst = first[t] + 1。
- 设置 bestLast = Last[t]。
(bestFirst, bestLast) 中将返回最大长度范围,或者如果不存在这样的范围,则这些变量都将为 -1。
我记得不久前在某处看到过这个解决方案,或者一个与它非常相似的解决方案——如果有人能找到它,我很乐意链接到它。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)