leetcode
leetcode 1651 ~ 1700
所有元音按顺序排布的最长子字符串

所有元音按顺序排布的最长子字符串

难度:

标签:

题目描述

代码结果

运行时间: 124 ms, 内存: 24.0 MB


/*
 * 思路:
 * 1. 使用流处理方法遍历字符串。
 * 2. 使用变量记录当前的元音顺序和计数器。
 * 3. 当检测到一个新的元音字符时,检查其是否符合字典序的要求,
 *    如果符合,继续;否则,重置当前记录。
 * 4. 记录最长的符合条件的子字符串长度。
 */
import java.util.stream.IntStream;

public int longestBeautifulSubstring(String word) {
    String vowels = "aeiou";
    int[] result = {0, 0, 0, 'a' - 1}; // {maxLength, currentLength, vowelCount, prevChar}

    IntStream.range(0, word.length()).forEach(i -> {
        char c = word.charAt(i);
        if (vowels.indexOf(c) == -1) return;
        if (c > result[3]) {
            result[3] = c;
            result[2]++;
        }
        if (vowels.indexOf(c) == vowels.indexOf((char)result[3])) {
            result[1]++;
        } else {
            result[1] = (c == 'a') ? 1 : 0;
            result[2] = (c == 'a') ? 1 : 0;
            result[3] = c;
        }
        if (result[2] == 5) {
            result[0] = Math.max(result[0], result[1]);
        }
    });

    return result[0];
}

解释

方法:

此题解采用了两个关键步骤来找到最长的美丽子字符串。首先,使用groupby函数从itertools库来聚合连续相同的字符,从而便于后续处理。第二步,将原字符串中连续相同的字符压缩成一个字符形成新的字符串ch_str,并将每组字符的长度存入列表g_list。然后,此解法通过在ch_str中找到'aeiou'这一特定模式的所有出现位置,并计算出从每个位置开始的连续五组字符的总长度,这样可以确保找到的子字符串符合美丽字符串的要求。最后,比较所有符合条件的子字符串长度,返回最长的一个。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在处理字符串时首先使用groupby来聚合连续相同的字符?这样做有什么好处?
使用groupby聚合连续相同的字符可以简化字符串的结构,将连续相同的字符视为一个整体。这样做有助于减少后续处理的复杂度,因为在寻找特定模式(如'aeiou')时,我们可以忽略单个字符的重复,只关注字符种类的变化,从而更加直观和高效地判断模式的出现。
🦆
在创建ch_str时,为什么选择将连续相同的字符压缩成一个字符,这对找出最长美丽子字符串有何影响?
将连续相同的字符压缩成一个字符主要是为了更容易地识别和处理连续的不同字符序列,特别是对于本题要求的'aeiou'顺序排列的子字符串。这种压缩使得在ch_str中直接用字符串查找函数(如find)就能快速定位到这一模式,从而简化了代码逻辑,提高了算法效率。对于最长美丽子字符串的寻找,这样的处理允许我们直接根据模式匹配的位置,快速计算出原字符串中相应部分的长度。
🦆
题解中提到,计算ch_str中'aeiou'模式出现的次数和位置,这种方法是否能确保每个'aeiou'都代表一个完整的并且符合条件的子字符串?
题解中通过计算ch_str中'aeiou'模式的出现确实可以找到所有可能的美丽子字符串的起始位置,但这种方法本身不能保证每个找到的'aeiou'之后还有足够的字符来构成完整的子字符串。因此,还需要额外的逻辑来验证每个模式后是否有足够的字符组成完整的美丽子字符串,这通常涉及到边界条件的检查。
🦆
在计算每个'aeiou'开始的五个组合字符的总长度时,如何处理边界情况,比如'aeiou'模式出现在字符串末尾或长度不足五个字符的情况?
在处理边界情况时,首先需要检查'aeiou'模式后是否还有足够的字符组存在。如果'aeiou'模式出现在字符串末尾或后续字符组不足五个,则这种情况下的'aeiou'模式不能构成有效的美丽子字符串。解决方法是在遍历ch_str时,每次找到'aeiou'后,检查后续是否还有足够的字符组(至少四个),只有在满足这个条件时,才计算这五个字符组的总长度。这种检查确保了每次计算的都是有效且完整的美丽子字符串。

相关问题