leetcode
leetcode 1151 ~ 1200
兼具大小写的最好英文字母

兼具大小写的最好英文字母

难度:

标签:

题目描述

代码结果

运行时间: 26 ms, 内存: 16.1 MB


/*
 * 思路:
 * 1. 使用stream来简化处理字符串中的字符。
 * 2. 将字符串转化为字符stream并收集到set中。
 * 3. 使用反向的range和filter来查找满足条件的字母。
 */
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public String bestLetter(String s) {
        Set<Character> charSet = s.chars().mapToObj(c -> (char)c).collect(Collectors.toSet());
        return IntStream.rangeClosed('A', 'Z')
                .mapToObj(c -> (char)('Z' - (c - 'A')))
                .filter(c -> charSet.contains(c) && charSet.contains(Character.toLowerCase(c)))
                .findFirst()
                .map(String::valueOf)
                .orElse("");
    }
}

解释

方法:

此题解首先生成两个列表,一个包含所有小写英文字母(lowalp_list),另一个包含所有大写英文字母(upalp_list)。对于每个字母,代码检查其大写和小写形式是否都在输入字符串s中出现。如果都出现,则将该字母的大写形式添加到列表lst中。遍历完成后,如果lst非空,返回lst中的最后一个元素,即字母表中最后一个同时具有大小写形式出现在s中的字母。如果lst为空,返回空字符串。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么选择使用两个列表分别存储小写和大写字母,而不是直接在循环中使用ASCII值进行字符的转换?
使用两个列表分别存储小写和大写字母的主要原因是为了代码的可读性和简便性。通过预先定义好的小写字母和大写字母列表,可以直接通过索引来访问对应的字母,无需在每次循环中进行ASCII值的计算和转换,这样可以使代码更加清晰易懂。虽然直接使用ASCII值进行转换也是可行的,但这通常会使代码复杂度稍增,特别是对于不熟悉ASCII编码的人来说,直接看到字符列表比计算ASCII值更直观。
🦆
在题解中,每检查一个字母是否存在于字符串s中,都会进行一次遍历。这样的时间复杂度是否可以优化?
是的,这样的时间复杂度确实可以优化。在当前的实现中,对于每一个字母,代码都会在字符串s中进行一次搜索,这使得时间复杂度达到O(26*n),其中n是字符串s的长度。一个更高效的方法是首先使用一个集合来存储字符串s中出现的所有字符,这个操作的时间复杂度是O(n)。然后,只需要检查每个字母的大小写是否都在这个集合中,这个检查的时间复杂度是O(1),因此总的时间复杂度将降低到O(n)。
🦆
题解中使用了一个列表lst来存储符合条件的字母,是否有更高效的方法来直接找到最后一个符合条件的字母?
确实存在更高效的方法来直接找到最后一个符合条件的字母。由于题目中指出需要返回字母表中最后一个符合条件的字母,我们可以从字母表的末尾开始向前检查每个字母。这样,一旦我们找到第一个即字母表中最后一个符合条件的大小写字母,我们可以立即停止搜索。这避免了使用额外的列表来存储所有符合条件的字母,从而节省了空间并可能减少一些运行时间,因为一旦找到符合条件的字母就可以停止循环。

相关问题