文章目录
题目
标题和出处
标题：检测大写字母
出处：520. 检测大写字母
难度
2 级
题目描述
要求
我们定义，在以下情况时，单词的大写用法是正确的：
- 全部字母都是大写，比如 "USA" \texttt{"USA"} "USA"。
- 单词中所有字母都不是大写，比如 "leetcode" \texttt{"leetcode"} "leetcode"。
- 如果单词不只含有一个字母，只有首字母大写，比如 "Google" \texttt{"Google"} "Google"。
给定一个字符串 word \texttt{word} word，如果单词的大写用法是正确的，返回 true \texttt{true} true。
示例
示例 1：
输入：
word
=
"USA"
\texttt{word = "USA"}
word = "USA"
输出：
true
\texttt{true}
true
示例 2：
输入：
word
=
"FlaG"
\texttt{word = "FlaG"}
word = "FlaG"
输出：
false
\texttt{false}
false
数据范围
- 1 ≤ word.length ≤ 100 \texttt{1} \le \texttt{word.length} \le \texttt{100} 1≤word.length≤100
- word \texttt{word} word 由大写和小写英语字母组成
解法
思路和算法
这道题目的最直观的解法是分别按照三条规则检查字符串 word \textit{word} word，只要符合其中的一条规则，即为大写用法正确。该解法最多需要遍历字符串三次，对于长度为 n n n 的字符串，时间复杂度是 O ( n ) O(n) O(n)。
检查字符串的大写用法是否正确不一定需要遍历整个字符串，如果在遍历过程中发现不符合大写用法，可提前返回，虽然时间复杂度仍然是 O ( n ) O(n) O(n)，最坏情况下还是需要遍历整个字符串，但是在大多数情况下都可以减少运行时间。
提前返回的情况包括以下两种：
-
首字母大写，其余字母既有大写又有小写；
-
首字母小写，其余字母有大写。
根据上述两种情况，可以首先判断首字母的大小写情况，然后遍历字符串。首字母大写和小写的情况分别处理如下：
-
如果首字母大写，则计数其余字母中的大写字母数量，当遍历到下标 i i i 时，除了首字母以外的大写字母数量应为 i i i（全部是大写）或 0 0 0（只有首字母大写），如果大写字母的数量不等于 0 0 0 且不等于 i i i，则说明既有大写又有小写，返回 false \text{false} false；
-
如果首字母小写，则其余字母中只要有一个大写，则返回 false \text{false} false。
当遍历结束时如果没有发现大写用法不正确的情况，则返回 true \text{true} true。
代码
class Solution {
public boolean detectCapitalUse(String word) {
int length = word.length();
boolean firstCapital = isCapital(word.charAt(0));
if (firstCapital) {
int capitalCount = 0;
for (int i = 1; i < length; i++) {
if (isCapital(word.charAt(i))) {
capitalCount++;
}
if (capitalCount != 0 && capitalCount != i) {
return false;
}
}
} else {
for (int i = 1; i < length; i++) {
char c = word.charAt(i);
if (isCapital(c)) {
return false;
}
}
}
return true;
}
public boolean isCapital(char c) {
return c >= 'A' && c <= 'Z';
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是字符串 word \textit{word} word 的长度。对于每个字符判断是否是大写字母的时间复杂度是 O ( 1 ) O(1) O(1)，最坏情况下需要遍历整个字符串 word \textit{word} word 一次，因此总时间复杂度是 O ( n ) O(n) O(n)。
-
空间复杂度： O ( 1 ) O(1) O(1)。