兼具大小写的最好英文字母【LC2309】
Given a string of English letters s, return the greatest English letter which occurs as both a lowercase and uppercase letter in s. The returned letter should be in uppercase. If no such letter exists, return an empty string.
An English letter b is greater than another letter a if b appears after a in the English alphabet.
DAY100啦 最近家里事情好多 哎
- 思路:使用int数组记录每个字母的大小写形式是否出现过,若小写出现过那么最低位为1,若大写出现过那么第二位为1,因此如果某个字母的大小写都出现在字符串中,那么哈希表中数值为3。倒叙遍历字母表,返回首个哈希表值等于3的字母的大写形式即可
- 实现
class Solution { public String greatestLetter(String s) { String ans = ""; int[] map = new int[26]; for (char c : s.toCharArray()){ if (c >= 'a' && c <= 'z'){ map[c - 'a'] |= 1; }else{ map[c - 'A'] |= 2; } } for (int i = 25; i >= 0; i--){ if (map[i] == 3){ ans += (char)('A' + i); return ans; } } return ans; } }
。复杂度
- 时间复杂度:O(n+C),n、m为字符串长度
- 空间复杂度:O(C),C为字符集大小,本题中为26
- 实现:使用两个int类型变量记录每个字母的大小写是否出现过
class Solution { public: string greatestLetter(string s) { int lower = 0, upper = 0; for (auto c : s) { if (islower(c)) { lower |= 1 << (c - 'a'); } else { upper |= 1 << (c - 'A'); } } for (int i = 25; i >= 0; i--) { if (lower & upper & (1 << i)) { return string(1, 'A' + i); } } return ""; } }; 作者:力扣官方题解 链接:https://leetcode.cn/problems/greatest-english-letter-in-upper-and-lower-case/solutions/2076006/jian-ju-da-xiao-xie-de-zui-hao-ying-wen-o5u2s/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
。复杂度
- 时间复杂度:O(n+C),n、m为字符串长度,C为字符集大小,本题中为26
- 空间复杂度:O(1)